01背包

01背包

例题中已知条件有第ii个物品的重量ww,价值viv_i,以及背包的总容量WW

设 DP 状态f(i,j)f(i,j)为在只能放前ii个物品的情况下,容量为jj的背包所能达到的最大总价值。

简要分析

每件物品都有两种状态:放和不放。

不放的状态转移则方程:f[i,j]=f[i1,j]f[i, j] = f[i-1, j]

的状态转移方程:f[i,j]=f[i1,jw[i]]+v[i]f[i, j] = f[i-1, j-w[i]] + v[i]

在每次转移过程中都选取最大的那个即可,即maxmax

朴素算法

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);

注意事项

  1. 为什么要枚举WW
    因为在选取的过程中,剩余空间可以是[0,W][0, W]中的任意值。

  2. 为什么使用滚动数组优化后要倒着枚举WW

    因为在去掉了一维之后,之前的状态i1i-1和当前的状态ii在同一行,而我们的f[jw[i]]f[j-w[i]]则依赖之前的状态,如果顺序枚举的话则会在选择之前覆盖掉。