资源描述：
《01背包解析和程序》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、01背包解析和程序 [问题描述] 在M件物品取出若干件放在空间为W的背包里，每件物品的体积为W1，W·2……Wn，与之相对应的价值为P1,P2……Pn。求出获得最大价值的方案。 注意：在本题中，所有的体积值均为整数。 [算法分析]： 对于背包问题，通常的处理方法是搜索。 用递归来完成搜索，算法设计如下： functionMake(i{处理到第i件物品},j{剩余的空间为j}:integer):integer; 初始时i=m,j=背包总容量 begin ifi:=0then Make:=0; ifj>=w
2、ithen(背包剩余空间可以放下物品i) r1:=Make(i-1,j-wi)+v;(第i件物品放入所能得到的价值) r2:=Make(i-1,j) (第i件物品不放所能得到的价值) Make:=max{r1,r2} end; 这个算法的时间复杂度是O(2^n)，我们可以做一些简单的优化。 由于本题中的所有物品的体积均为整数，经过几次的选择后背包的剩余空间可能会相等，在搜索中会重复计算这些结点，所以，如果我们把搜索过程中计算过的结点的值记录下来，以保证不重复计算的话，速度就会提高很多。这是简单?quot;以空间换时
3、间"。 我们发现，由于这些计算过程中会出现重叠的结点，符合动态规划中子问题重叠的性质。 同时，可以看出如果通过第N次选择得到的是一个最优解的话，那么第N-1次选择的结果一定也是一个最优解。这符合动态规划中最优子问题的性质。 考虑用动态规划的方法来解决，这里的： 阶段是：在前N件物品中，选取若干件物品放入背包中； 状态是：在前N件物品中，选取若干件物品放入所剩空间为W的背包中的所能获得的最大价值； 决策是：第N件物品放或者不放； 由此可以写出动态转移方程： 我们用f[i,j]表示在前i件物品中选择若干件放在所剩空
4、间为j的背包里所能获得的最大价值 f[i,j]=max{f[i-1,j-Wi]+Pi(j>=Wi),4f[i-1,j]} 这样，我们可以自底向上地得出在前M件物品中取出若干件放进背包能获得的最大价值，也就是f[m,w] 算法设计如下： procedureMake; begin fori:=0towdo f[0,i]:=0; fori:=1tomdo forj:=0towdobegin f[i,j]:=f[i-1,j]; if(j>=w)and(f[i-1,j-w]+v>f[i,j])then f[i,j
5、]:=f[i-1,j-w]+v; end; writeln(f[m,wt]); end; 由于是用了一个二重循环，这个算法的时间复杂度是O（n*w)。而用搜索的时候，当出现最坏的情况，也就是所有的结点都没有重叠，那么它的时间复杂度是O（2^n)。看上去前者要快很多。但是，可以发现在搜索中计算过的结点在动态规划中也全都要计算，而且这里算得更多（有一些在最后没有派上用场的结点我们也必须计算），在这一点上好像是矛盾的。 事实上，由于我们定下的前提是：所有的结点都没有重叠。也就是说，任意N件物品的重量相加都不能相等，而所有物
6、品的重量又都是整数，那末这个时候W的最小值是：1+2+2^2+2^3+……+2^n-1=2^n-1 此时n*w>2^n，动态规划比搜索还要慢~~
7、
8、
9、
10、
11、
12、
13、所以，其实背包的总容量W和重叠的结点的个数是有关的。 考虑能不能不计算那些多余的结点…… 题目 有N件物品和一个容量为V的背包。第i件物品的费用是c，价值是w。求解将哪些物品装入背包可使价值总和最大。 基本思路 这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。 用子问题定义状态：即f[v]表示前i件物品恰放入一个容量为v的背包可以获得的最大
14、价值。则其状态转移方程便是： f[v]=max{f[v],f[v-c]+w} 这个方程非常重要，基本上所有跟背包相关的问题的方程都是由它衍生出来的。所以有必要将它详细解释一下：“将前i件物品放入容量为4v的背包中”这个子问题，若只考虑第i件物品的策略（放或不放），那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第i件物品，那么问题就转化为“前i-1件物品放入容量为v的背包中”，价值为f[v]；如果放第i件物品，那么问题就转化为“前i-1件物品放入剩下的容量为v-c的背包中”，此时能获得的最大价值就是f[v-c]再加
15、上通过放入第i件物品获得的价值w。 优化空间复杂度 以上方法的时间和空间复杂度均为O(N*V)，其中时间复杂度基本已经不能再优化了，但空间复杂度却可以优化到O(V)。 先考虑上面讲的基本思路如何实现，肯定是有一个主循环i=1..N，每次算出来二维数组f[0..V]的所有
