背包问题学习笔记(1)

时间:2022-11-01 18:42:05

背包问题学习笔记(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的背包可能被价值为0nothing“恰好装满”,
       其它容量的背包均没有合法的解,属于未定义的状态,它们的值就都应该是-∞了。
    2. 如果背包并非必须被装满,那么任何容量的背包都有一个合法解“什么都不装”,这个解的价值
       为0,所以初始时状态的值也就全部为0