动态规划 -- 背包问题 - (sunznx) 振翅飞翔
27 October 2019

01 背包

dp[i][j] 表示背包体积为 j 时,物品 0~i 的总价值最大是多少
可以将 dp[i][j] 分为两个集合:

  1. 不取 第 i 个物品
  2. 取第 i 个物品
dp[i][j] = max(dp[i-1][j], dp[i-1][j-V[i]] + W[i])

for (int i = 1; i <= n; i++) {
    for (int j = 0; j <= v; j++) {
        if (j >= V[i]) {
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-V[i]] + W[i]);
        } else {
            dp[i][j] = dp[i-1][j];
        }
    }
}

更好的写法

for (int i = 1; i <= n; i++) {
    for (int j = 0; j <= v; j++) {
        dp[i][j] = dp[i-1][j];
        if (j >= V[i]) {
            dp[i][j] = max(dp[i][j], dp[i-1][j-V[i]] + W[i]);
        }
    }
}

空间优化,滚动数组:
两层循环中,我们只用到了 dp[i][x]dp[i-1][x] ,可以用一个二维的数组来表示

dp[i%2] = max(dp[(i-1)%2][j], dp[(i-1)%2][j-V[i]] + W[i])

空间优化,一维数组:
j 是从 V[i] 开始的,因此,我们的代码可以写成这样:

for (int i = 1; i <= n; i++) {
    for (int j = 0; j <= v; j++) {
        dp[i][j] = dp[i-1][j];
    }

    for (int j = V[i]; j <= v; j++) {
        dp[i][j] = max(dp[i][j], dp[i][j-V[i]] + W[i]);
    }
}

可以发现,我们是有机会将 dp[i][j] 优化成 dp[j] 的形式:

for (int i = 1; i <= n; i++) {
    for (int j = V[i]; j <= v; j++) {
        dp[j] = max(dp[j], dp[j-V[i]] + W[i]);
    }
}

现在 dp[j] 表示的有两层意思:

  1. 背包体积为 j 时,上次能取到的总价值最大是多少
  2. 背包体积为 j 时,当前能取到的总价值最大是多少

j-V[i] 是从 0 开始递增的, j 是从 V[i] 开始递增的,第二层循环中,每次都是修改的 dp[j] ,当 j-V[i] 递增到 V[i] 的时候,就会发现 dp[j-V[i]] 已经被修改了

for (int i = 1; i <= n; i++) {
    for (int j = v; j >= V[i]; j--) {
        dp[j] = max(dp[j], dp[j-V[i]] + W[i]);
    }
}

写成这种形式:
j 从 v 开始递减,我们每次修改 dp[j] 的时候并不会影响到 dp[j-V[i]]

完全背包

dp[i][j] 表示背包体积为 j 时,物品 0~i 的总价值最大是多少
可以将 dp[i][j] 分为 k+1 个集合,分别是取第 i 个物品 {0,1,2,…, k} 次,求 dp[i][j-V[i]*k] 的最大值

for (int i = 1; i <= n; i++) {
    for (int j = 0; j <= v; j++) {
        dp[i][j] = dp[i-1][j];
        for (int k = 1; k*V[i] <= j; k++) {
            dp[i][j] = max(dp[i][j], dp[i-1][j-V[i]*k] + W[i]*k);
        }
    }
}
cout << dp[n][v];

转换成二维:
首先,我们知道 dp[i][j] 可以用如下表示:

dp[i][j] = max{dp[i-1][j-V[i]*0], dp[i-1][j-V[i]*1]+W[i]*1, dp[i-1][j-V[i]*2]+W[i]*2, ..., dp[i-1][j-V[i]*k]+W[i]*k}

dp[i][j-V[i]] 可以用如下表示:

dp[i][j-V[i]] = max{dp[i-1][j-V[i]], dp[i-1][j-V[i]*2]+W[i], ..., dp[i-1][j-V[i]*k]+W[i]*(k-1)}

dp[i][j]      = max{dp[i-1][j-V[i]*0], dp[i-1][j-V[i]*1]+W[i]*1, dp[i-1][j-V[i]*2]+W[i]*2, ..., dp[i-1][j-V[i]*k]+W[i]*k}
dp[i][j-V[i]] = max{                   dp[i-1][j-V[i]],          dp[i-1][j-V[i]*2]+W[i],   ..., dp[i-1][j-V[i]*k]+W[i]*(k-1)}

==> dp[i][j] = max{dp[i-1][j-V[i]*0], dp[i][j-V[i]]+W[i]}
==> dp[i][j] = max{dp[i-1][j], dp[i-1][j-V[i]]+W[i]}

空间优化,一维数组:
j 是从 V[i] 开始的,因此,我们的代码可以写成这样:

for (int i = 1; i <= n; i++) {
    for (int j = 0; j <= v; j++) {
        dp[i][j] = dp[i-1][j];
    }

    for (int j = V[i]; j <= v; j++) {
        dp[i][j] = max(dp[i][j], dp[i][j-V[i]] + W[i]);
    }
}

dp[i][j] 写成 dp[j] :

for (int i = 1; i <= n; i++) {
    for (int j = V[i]; j <= v; j++) {
        dp[j] = max(dp[j], dp[j-V[i]]+W[i]);
    }
}

为什么这个是正确的:
dp[j] 表示体积为 j 时,所能取的最大价值。
假设 j 为 2*V[i]dp[j] 表示的有可能有如下几种选择方式:

  1. 第 i 个物品的数目为 0
  2. 第 i 个物品的数目为 1
  3. 第 i 个物品的数目为 2

继续假设现在 j2*V[i] ,我们要求此时的 dp[j] ,dp[j] 就必须在 [V[i], 2*V[i]) 这个区间内更新过。因此遍历的时候, jV[i] 递增到 v
而 “01 背包” 的时候,我们要求此时的 dp[j][V[i], 2*V[i]) 这个区间内是没更新过。因此遍历的时候, jv 递增到 V[i]

多重背包

朴素写法(当成是 01 背包)

for (int i = 1; i <= n; i++) {
    for (int j = 0; j <= v; j++) {
        dp[i][j] = dp[i-1][j];
        for (int k = 1; k <= S[i]; k++) {
            if (j >= k*V[i]) {
                dp[i][j] = max(dp[i][j], dp[i-1][j-V[i]*k] + W[i]*k);
            }
        }
    }
}

二进制分解思路:
假设 S[i]=9 ,即意味着我们可以往背包装 {0,1,2,3,…,9} 个 i 物品,二进制分解的思路是将这 9 个 i 物品进行合并。合并成如下几种:
S1=1,S2=2,S3=4,S4=2 ,Sn=k 表示第 n 个物品有 k 个 i 物品

二进制分解能将 {1,2,3,…,9} 全部遍历一次,即对新的 4 个物品进行 01 背包计算,能将 {1,2,…,9} 可能出现的情况都计算一次,例如

1=S1
2=S2
3=S1 + S2
4=S3
5=S1 + S3
6=S2 + S3
7=S1 + S2 + S3
8=S2 + S3 + S4
9=S1 + S2 + S3 + S4

int newN = 0;
for (int i = 1; i <= n; i++) {
    int p = 1;
    int s = S[i];
    int k;
    while (s > 0) {
        if (s >= p) {
            newN++;
            newV[newN] = V[i] * p;
            newW[newN] = W[i] * p;
        } else {
            newN++;
            newV[newN] = V[i] * s;
            newW[newN] = W[i] * s;
        }
        s = s - p;
        p = p * 2;
    }
}

for (int i = 1; i <= newN; i++) {
    for (int j = v; j >= newV[i]; j--) {
        dp[j] = max(dp[j], dp[j-newV[i]] + newW[i]);
    }
}

分组背包

直接当成 01 背包

for (int i = 1; i <= n; i++) {
    for (int j = 0; j <= v; j++) {
        dp[i][j] = dp[i-1][j];
        for (int k = 1; k <= S[i]; k++) {
            if (j >= V[i][k]) {
                dp[i][j] = max(dp[i][j], dp[i-1][j-V[i][k]] + W[i][k]);
            }
        }
    }
}

优化

for (int i = 1; i <= n; i++) {
    for (int j = v; j >= 0; j--) {
        for (int k = 1; k <= S[i]; k++) {
            if (j >= V[i][k]) {
                dp[j] = max(dp[j], dp[j-V[i][k]] + W[i][k]);
            }
        }
    }
}