关于pascal 背包问题 f[j]:=max(f[j],f[j-c[i]]+w[i]); 是什么意思 其...
发布网友
发布时间：2024-08-19 06:25
我来回答
共1个回答
热心网友
时间：2024-08-30 05:03
你这个是01背包的吧？ 首先要明白二维的写法，即f[i,v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是：f[i,v]=max{f[i-1,v],f[i-1,v-c[i]]+w[i]}。 这个应该很好理解吧， 然后考虑上面讲的基本思路如何实现： 肯定是有一个主循环i=1..N，每次算出来二维数组f[i,0..V]的所有值。 那么，如果只用一个数组f[0..V]，能不能保证第i次循环结束后f[v]中表示的就是我们定义的状态f[i,v]呢？ f[i,v]是由f[i-1,v]和f[i-1,v-c[i]]两个子问题递推而来，能否保证在推f[i][v]时（也即在第i次主循环中推f[v]时）能够得到f[i-1,v]和f[i-1,v-c[i]]的值呢？事实上，这要求在每次主循环中我们以v=V..0的顺序推f[v]，这样才能保证推f[v]时f[v-c[i]]保存的是状态f[i-1][v-c[i]]的值。伪代码如下： for i=1..N for v=V..0 f[v]=max{f[v],f[v-c[i]]+w[i]}; 其中的f[v]=max{f[v],f[v-c[i]]}一句恰就相当于我们的转移方程f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]}，因为现在的f[v-c[i]]就相当于原来的f[i-1][v-c[i]]。如果将v的循环顺序从上面的逆序改成顺序的话，那么则成了f[i][v]由f[i][v-c[i]]推知，与本题意不符，但它却是另一个重要的背包问题P02最简捷的解决方案，故学习只用一维数组解01背包问题是十分必要的。
