01背包

发表于 更新于 分类于 阅读次数： Disqus：

01背包

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

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

简要分析

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

不放的状态转移则方程：f[i,j]=f[i−1,j]f[i, j] = f[i-1, j]。

放的状态转移方程：f[i,j]=f[i−1,j−w[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？

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