01背包

· · 个人记录

01 背包

一、概念

01 背包是指：有 n 件物品，每件物品的重量为 w_i，价值为 p_i。现在有一个容量为 m 的背包，在不超过背包容量的情况下，求最大价值。每种物品最多只能放一件。

二、思路

设 f[i][j] 为容量为 j 的背包中放前 i 件物品所能获得的最大价值。

放每种物品时，有三种情况：

即：

\begin{Bmatrix} f[i][j]=f[i-1][j](1 \leq j<w[i])\\ f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+p[i])(w[i] \leq j \leq m) \end{Bmatrix}

举例分析

n=3,m=6

如上表，最终答案为 9。

处理过程及输出代码

for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
        if (j < w[i])   f[i][j] = f[i-1][j];
        else    f[i][j] = max(f[i-1][j],f[i-1][j-w[i]]+p[i]);
    }
}
cout << f[n][m] << endl;

三、优化

按照以上解法，时间复杂度为 O(nm)，不可优化；而空间复杂度为 O(nm)，可将 f 数组压至一维数组，使空间复杂度调至 O(m)。这种技巧称为滚动数组。

思路

设 f[j] 为容量为 j 的背包中放若干件物品所能获得的最大价值。

放每种物品时，有三种情况：

即：

f[j]=max(f[j],f[j-w[i]]+p[i])(m \geq j \geq w[i])

值得要注意的是：内层循环必须逆序。

处理过程及输出代码

for (int i = 1; i <= n; i++) {
    for (int j = m; j >= w[i]; j--) {
        f[j] = max(f[j],f[j-w[i]]+p[i]);
    }
}
cout << f[m] << endl;

板子题：AT_dp_d Knapsack 1

四、练习