01背包问题

Problem

有 N 件物品和一个容量为 V 的背包。第i件物品的费用是 c[i],价值是 w[i]。求解将哪些物品装入背包可使价值总和最大。

Analysis

每次问题仅有一件,可以选择放或者不放。

然后变成一个 DP 问题,用一个 f[i][v] 表示前 i 件物品放入容量为 v 的背包获得的价值,状态转移方程:

$$f[i][v] = max(f[i-1][v], f[i-1][v - c[i]] + w[i])$$

时间复杂度 $O(NV)$,空间复杂度 $O(NV)$。

空间优化

空间可以优化成 $O(V)$。

因为计算完了 f[i] 时,只用到了 f[i-1],f[i-2] 已经没用了,所以优化成一维数组 (滚动数组) ,

$$f[v] = max(f[v], f[v-c[i]] + w[i])$$

初始化的细节问题

  • 不要求恰好装满,f[i] 全部初始化为 0。
  • 要求恰好装好装满,除 f[0] 为 0,其余全部初始化为 $-\infty$。

一个常数优化

此时的伪代码:

1
2
3
4
f[0] = 0
for i=1...n
for v=V...c[i]
f[v]=max{f[v],f[v-c[i]]+w[i]}
  • 每一层在 v < c[i] 时,就不需要往下继续算了,因为肯定不放第 i 个物品了。
  • 可以发现,在最后的一层遍历中中,只用求出 f[V] 就好了,不需要在遍历到前面了,倒数第一层只需要知道 f[V-c[n]] 的值就好了,也就是说倒数第二层只需要算到 f[V-c[n]],就可以给倒数第一层用了,那继续推,倒数第三层只要算到 f[V-c[n]-c[n-1]] 就可以满足倒数第二层的需求了。

优化后:

1
2
3
4
for i=1...n
bound=max{c[i], V-sum(c[i+1...n])}
for v=V...bound
f[v]=max{f[v],f[v-c[i]]+w[i]}

此优化在 V 非常大时比较有用。

其他

  • 求出那些物品被放了,那些物品没被放?
    • 这种就要用二维数组来记录 dp 了,从右下角 f[N][V] 开始遍历,如果 f[i][v] == f[i-1][v] 说明没放,反之放了,然后一直遍历到左上角 f[0][0] 为止
  • 求出第 K 优的解?
    • 为 f[] 数组加一维,用来存放前 K 优解,每次更新的时候,按放入 i 个物品的前 K 优解和未放入 i 个物品的前 K 优解重新排序一波,然后将 K 优解放入 f[i]
    • 相当于找出两个班的前 K 名,需要把两个班的前 K 名都拿出来

Summary

上次笔试题做到一个类似 01 背包的问题,然后没 A 掉。。我还记得我大二的时候还做过关于动态规划的 ppt,01 背包还是我当时的案例。。现在。。我恨。。

学一次,忘一次。。这次要记下来。

References