搜索
动态规划0/1背包问题【0/1背包问题】在0/1背包问题中，需对容量为c的背包进行装载。从n个物品中选取装入背包的物品，每件物品i的重量为wi，价值为pi。对于可行的背包装载，背包中物品的总重量不能超过背包的容量，最佳装载是指所装入的物品价值最高，即p1*x1+p2*x1+...+pi*xi(其1=i=n，x取0或1，取1表示选取物品i)取得最大值。【输入文件】第一行一个数c，为背包容量。第二行一个数n，为物品数量第三行n个数，以空格间隔，为n个物品的重量第四行n个数，以空格间隔，为n个物品的价值【输出文件】能取得的最大价值。【分析】初看这类问题，第一个想到的会是贪心，但是贪心法却无法保证一定能得到最优解，看以下实例：贪心准则1：从剩余的物品中，选出可以装入背包的价值最大的物品，利用这种规则，价值最大的物品首先被装入（假设有足够容量），然后是下一个价值最大的物品，如此继续下去。这种策略不能保证得到最优解。例如，考虑n=2,w=[100,10,10],p=[20,15,15],c=105。当利用价值贪婪准则时，获得的解为x=[1,0,0]，这种方案的总价值为20。而最优解为[0,1,1]，其总价值为30。贪心准则2：从剩下的物品中选择可装入背包的重量最小的物品。虽然这种规则对于前面的例子能产生最优解，但在一般情况下则不一定能得到最优解。考虑n=2,w=[10,20],p=[5,100],c=25。当利用重量贪婪策略时，获得的解为x=[1,0],比最优解[0,1]要差。贪心准则3：价值密度pi/wi贪婪算法，这种选择准则为：从剩余物品中选择可装入包的pi/wi值最大的物品，但是这种策略也不能保证得到最优解。利用此策略解n=3,w=[20,15,15],p=[40,25,25],c=30时的得到的就不是最优解。由此我们知道无法使用贪心算法来解此类问题。我们采用如下思路：在该问题中需要决定x1..xn的值。假设按i=1，2，...，n的次序来确定xi的值。如果置x1=0，则问题转变为相对于其余物品(即物品2，3，.，n)，背包容量仍为c的背包问题。若置x1=1，问题就变为关于最大背包容量为c-w1的问题。现设r={c，c-w1}为剩余的背包容量。在第一次决策之后，剩下的问题便是考虑背包容量为r时的决策。不管x1是0或是1，[x2，.，xn]必须是第一次决策之后的一个最优方案。也就是说在此问题中，最优决策序列由最优决策子序列组成。假设f(i,j)表示剩余容量为j，剩余物品为i，i+1，...，n时的最优解的值，即：利用最优序列由最优子序列构成的结论，可得到f的递归式为：当j≥wi时：f(i,j)=max{f(i+1,j),f(i+1,j-wi)+pi}当0≤jwi时：f(i,j)=f(i+1,j)这是一个递归的算法，其时间效率较低，为指数级。考虑用动态规划的方法来解决:阶段：在前i件物品中，选取若干件物品放入背包中；状态：在前i件物品中，选取若干件物品放入所剩空间为c的背包中的所能获得的最大价值；决策：第i件物品放或者不放；由此可以写出动态转移方程：用f[i,j]表示在前i件物品中选择若干件放在所剩空间为j的背包里所能获得的最大价值f[i,j]=max{f[i-1,j-wi]+pi(j=wi),f[i-1,j]}这样，就可以自底向上地得出在前n件物品中取出若干件放进背包能获得的最大价值，也就是f[n,c]算法框架如下：fori:=0tocdo{i=0也就是没有物品时清零}f[0,i]:=0;fori:=1tondo{枚举n件物品}forj:=0tocdo{枚举所有的装入情况}beginf[i,j]:=f[i-1,j];{先让本次装入结果等于上次结果}if(j=w[i])and(f[i-1,j-w[i]]+p[i]f[i,j]){如果能装第i件物品}thenf[i,j]:=f[i-1,j-w[i]]+p[i];{且装入后价值变大则装入}end;writeln(f[n,c]);为了进一步说明算法的执行原理，下面给出一个实例：【输入文件】104514340102530【输出结果】下面列出所有的f[i,j]0000404040404040101010104050505050501010102540505050657510103040405055708080从以上的数据中我们可以清晰地看到每一次的枚举结果，每一行都表示一个阶段。