背包问题学习笔记(1)
写在前面
一方面学习背包九讲:http://blog.csdn.net/pi9nc/article/details/8142876,这个十分清晰,重点标记清楚。
但有些需要自己理解的和重点的,我做了如下笔记,方便别人理解,也方便自己复习,如有错误,欢迎指正。
01背包问题
状态函数f[i][v] 表示==前i件物品放入容量为v的背包可获得的最大价值==
状态迁移方程
f[i][v] = max { f[i-1][v],f[i-1][v-c[i]]+w[i]}
考虑下为什么是这样的,对于第i件物品,我们只考虑是否要把这个放进去,这取决与两种情况:
1. 不放进去,那么前i-1件容量和最大可以是v -- f[i-1][v];
2. 放进去,那么前i-1件容量和最大为v-c[i] -- f[i-1][v-c[i]]+w[i]
以上方法==时间和空间复杂度均为O(N*V)==
可以优化空间复杂度为O(v):
for i = 1:N
for v = V:0
f[v] = max { f[v],f[v-c[i]]+w[i]};
TIPS:
注意由于i是从1:N,所以每当i增加1时,f[v]都之前的值,即f[i-1][v],因此需要V是逆序,这样f[v-c[i]]中才不会被修改(V-c[i]
01背包抽象
- 不一定需要从一开始,那样会浪费
ZeroOnePack 抽象优化
/** * @param cost i物品的费用 * @param weight i物品的价值 */
procedure ZeroOnePack(cost ,weight)
for v = V:cost
f[v] = max { f[v], f[v-cost]+weight}
初始化的细节问题
- 问法一: 要求恰好装满背包
- 初始化时,除了f[0]为0 其他f[i] (1<=i<=V)均设置为-∞
- 结果 最终的 f[n]是恰好装满的最优解
- 问法二: 没有要求背包装满,希望 Weight 和最大
- 初始化 f[i] (0<=i<=V)全部为0
- 最终的 f[n] 是最优解
Tips 初始化原因
1. 如果要求背包恰好装满,那么此时只有容量为0的背包可能被价值为0的nothing“恰好装满”,
其它容量的背包均没有合法的解,属于未定义的状态,它们的值就都应该是-∞了。
2. 如果背包并非必须被装满,那么任何容量的背包都有一个合法解“什么都不装”,这个解的价值
为0,所以初始时状态的值也就全部为0了