回溯法之0
回溯法解0-1背包问题
问题描述
输入：n件物品的价值和重量{<w1, v1>, <w2, v2>,…, <wn, vn>}和背包容量C
输出：(x1, x2, …, xn)，xi∈{0, 1}满足放入的物品重量小于背包容量的前提下价值最大
优化目标：价值最大化
实例讲解
假设：
物品个数为 n=3
背包的容量为 C=30
物品的重量分别为 w={16，15，15}
物品的价值分别为 v={45，25，25}
1.此时的解空间可以为(x1, x2, x3)的所有可能取{(0,0,0), (0,0,1), (0,1,0), (0,1,1), (1,0,0), (1,0,1), (1,1,0), (1,1,1)}
2.构造解空间树：
3.遍历解空间（深度优先）
从根往下遍历时，要求每次经过节点都计算此时是否满足容量的条件，当某个分支可以满足重量要求时，记录它的价值总量，以便最后选择最好的价值量。
例如第一次遍历时，经过x1=1，x2=1时，此时重量为31，超过了背包容量，那么我们回溯到x1=1处，并使用剪枝算法的约束函数剪去x2=1这个分支，并遍历x2=0这个分支，再从x2往下拓展x3=1或者0的情况。
概念介绍
扩展结点:一个正在产生儿子的结点称为扩展结点
活结点:一个自身已生成但其儿子还没有全部生成的节点称做活结点
死结点:一个所有儿子已经产生的结点称做死结点
深度优先的问题状态生成法：如果对一个扩展结点R，一旦产生了它的一个儿子C，就把C当做新的扩展结点。在完成对子树C（以C为根的子树）的穷尽搜索之后，将R重新变成扩展结点，继续生成R的下一个儿子（如果存在）
回溯法：为了避免生成那些不可能产生最佳解的问题状态，要不断地利用限界函数(bounding function)来处死那些实际上不可能产生所需解的活结点，以减少问题的计算量。具有限界函数的深度优先生成法称为回溯法
算法扩展-一般背包问题
在0-1背包中，物品不可拆分，但在一般背包中我们可以将物品拆分，例如将物品1的0.1部分装入背包。
解题思路：
将物品按照单位重量价值排序。先装价值高的，一直到背包装满为止。相关知识
DNF攻略：揭秘！赛丽亚时光回溯活动，隐藏宠物等你拿
DNF：真成宝宝巴士了！赛丽亚回溯活动现惊喜，隐藏宠物别错过
苍之纪元教你怎样才算真正精通游戏玩法
动物福利法：中国与欧盟之比较
绩效考核之行为锚定等级评价法
奥法（奥法高塔电梯）
自然后果惩罚法名词解释
4978:宠物小精灵之收服（0
《塞尔达传说王国之泪》吉乌可乌每神庙吻合之形过法攻略
猫咪牙齿耳朵眼睛之清洁法
网址: 回溯法之0 https://m.mcbbbk.com/newsview801937.html
| 上一篇: lc |
下一篇: vs2010 C语言遇到的问题 |
