01背包问题的多种解法.docVIP

问题描述 0/1背包问题: 现有n种物品，对1=i=n，已知第i种物品的重量为正整数Wi，价值为正整数Vi，背包能承受的最大载重量为正整数W，现要求找出这n种物品的一个子集，使得子集中物品的总重量不超过W且总价值尽量大。（注意：这里对每种物品或者全取或者一点都不取，不允许只取一部分） 算法分析 根据问题描述，可以将其转化为如下的约束条件和目标函数： 于是，问题就归结为寻找一个满足约束条件（1），并使目标函数式（2）达到最大的解向量。 首先说明一下0-1背包问题拥有最优解。 假设是所给的问题的一个最优解，则是下面问题的一个最优解：。如果不是的话，设是这个问题的一个最优解，则，且。因此，，这说明是所给的0-1背包问题比更优的解，从而与假设矛盾。 穷举法： 用穷举法解决0-1背包问题，需要考虑给定n个物品集合的所有子集，找出所有可能的子集（总重量不超过背包重量的子集），计算每个子集的总重量，然后在他们中找到价值最大的子集。由于程序过于简单，在这里就不再给出，用实例说明求解过程。下面给出了4个物品和一个容量为10的背包，下图就是用穷举法求解0-1背包问题的过程。 四个物品和一个容量为10的背包 序号 子集 总重量 总价值 序号 子集 总重量 总价值 1 空集 0 0 9 {2，3} 7 52 2 {1} 7 42 10 {2，4} 8 37 3 {2} 3 12 11 {3，4} 9 65 4 {3} 4 40 12 {1,2,3} 14 不可行 5 {4} 5 25 13 {1,2,4} 15 不可行 6 {1，2} 10 54 14 {1,3,4} 16 不可行 7 {1，3} 11 不可行 15 {2,3,4} 12 不可行 8 {1，4} 12 不可行 16 {1,2,3,4} 19 不可行 （b）用回溯法求解0-1背包问题的过程 递归法： 在利用递归法解决0-1背包问题时，我们可以先从第n个物品看起。每次的递归调用都会判断两种情况： 背包可以放下第n个物品，则x[n]=1，并继续递归调用物品重量为W-w[n],物品数目为n-1的递归函数，并返回此递归函数值与v[n]的和作为背包问题的最优解； 背包放不下第n个物品，则x[n]=0，并继续递归调用背包容量为W，物品数目为n-1的递归函数，并返回此递归函数值最为背包问题的最优解。 递归调用的终结条件是背包的容量为0或物品的数量为0.此时就得到了0-1背包问题的最优解。 用递归法解0-1背包问题可以归结为下函数： 第一个式子表示选择物品n后得到价值比不选择物品n情况下得到的价值小，所以最终还是不选择物品n;第二个式子刚好相反，选择物品n后的价值不小于不选择物品n情况下得到了价值，所以最终选择物品n。 在递归调用的过程中可以顺便求出所选择的物品。下面是标记物品被选情况的数组x[n]求解的具体函数表示： 在函数中，递归调用的主体函数为KnapSack，m表示背包的容量，n表示物品的数量，x[n]表示是否选择了第n个物品（1—选，0—不选）。每个物品的重量和价值信息分别存放在数组w[n]和v[n]中。具体的代码见《递归法》文件夹。 贪心法： 0-1背包问题与背包问题类似，所不同的是在选择物品装入背包时，可以选择一部分，而不一定要全部装入背包。这两类问题都具有最优子结构性质，相当相似。但是背包问题可以用贪心法求解，而0-1背包问题却不能用贪心法求解。贪心法之所以得不到最优解，是由于物品不允许分割，因此，无法保证最终能将背包装满，部分闲置的背包容量使背包单位重量的价值降低了。事实上，在考虑0-1背包问题时，应比较选择物品和不选择物品所导致的方案，然后做出最优解。由此导出了许多相互重叠的子问题，所以，0-1背包问题可以用动态规划法得到最优解。在这里就不再用贪心法解0-1背包问题了。 动态规划法分析： 0-1背包问题可以看作是寻找一个序列，对任一个变量 的判断是决定=1还是=0.在判断完之后，已经确定了，在判断时，会有两种情况： 背包容量不足以装入物品i，则=0，背包的价值不增加； 背包的容量可以装下物品i，则=1，背包的价值增加。 这两种情况下背包的总价值的最大者应该是对判断后的价值。令表示在前i个物品中能够装入容量为j的背包的物品的总价值，则可以得到如下的动态规划函数： 式（1）说明：把前面i个物品装入容量为0的背包和把0个物品装入容量为j的背包，得到的价值均为0.式（2）第一个式子说明：如果第i个物品的重量大于背包的容量，则装入第i个物品得到的最大价值和装入第i-1个物品得到的最大价值是相同的，即物品i不能装入背包中；第二个式子说明：如果第i个物品的重量小于背包的容量，则会有两种