01背包
例题中已知条件有第i个物品的重量w,价值vi,以及背包的总容量W。
设 DP 状态f(i,j)为在只能放前i个物品的情况下,容量为j的背包所能达到的最大总价值。
简要分析
每件物品都有两种状态:放和不放。
不放的状态转移则方程:f[i,j]=f[i−1,j]。
放的状态转移方程:f[i,j]=f[i−1,j−w[i]]+v[i]。
在每次转移过程中都选取最大的那个即可,即max。
朴素算法
1 2 3 4
| for (int i = 1; i <= n; i++) for (int j = 1; j <= W; j++) if (j >= a[i].w) f[i][j] = max(f[i-1][j], f[i-1][j-a[i].w] + a[i].v);
|
滚动数组优化
1 2 3 4
| for (int i = 1; i <= n; i++) for (int j = W; j >= 0; j--) if (j >= a[i].w) f[j] = max(f[j], f[j-a[i].w] + a[i].v);
|
注意事项
-
为什么要枚举W?
因为在选取的过程中,剩余空间可以是[0,W]中的任意值。
-
为什么使用滚动数组优化后要倒着枚举W?
因为在去掉了一维之后,之前的状态i−1和当前的状态i在同一行,而我们的f[j−w[i]]则依赖之前的状态,如果顺序枚举的话则会在选择之前覆盖掉。