动态规划 - 背包问题

01 背包

问题描述：

N 件物品，第 i 件物品的价值和占用体积分别为 W_i 和 C_i，背包容量为 V。求解把哪些物品放入背包能够获得最大价值且物品体积不超过背包容量。

思路：

每一件物品只有两种可能，放或者不放入背包。

转移方程：

dp[i, v] 表示前 i 件物品放入容量为 v 的背包所能得到的最大价值。

dp[i, v] = max(dp[i - 1, v], dp[i - 1, v - C[i]] + W[i])

代码：

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

优化：

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

完全背包

问题描述：

N 种数量无限的物品，第 i 种物品的价值和占用体积分别为 W_i 和 C_i，背包容量为 V。求解把哪些物品放入背包能够获得最大价值且物品体积不超过背包容量。

思路：

和 01 背包问题类似，只不过该问题中每种物品可放入多次。即对于一个物品来说，不是考虑放或不放入，而是考虑放入 0 件、1 件、2 件……V / C_i 件

转移方程：

dp[i, v] 表示前 i 件物品放入容量为 v 的背包所能得到的最大价值。

dp[i, v] = max(dp[i - 1, v - k * C[i]] + k * W[i]) (0 ≤ k ≤ v / C[i])

代码：

for (int i = 1; i <= N; i++) {
    for (int v = 0; v <= V; v++) {
        for (int k = 0; k <= v / C[i]; k++) {
            dp[i, v] = max(dp[i, v], dp[i - 1, v - k * C[i]] + k * W[i]);
        }
    }
}
return dp[N, V];

优化：

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

多重背包

问题描述：

N 种数量有限的物品，第 i 种物品的价值，占用体积和数量分别为 W_i，C_i 和 M_i，背包容量为 V。求解把哪些物品放入背包能够获得最大价值且物品体积不超过背包容量。

思路：

和完全背包问题类似，只不过该问题中每种物品并不是无限的而是有一个最大数量。

转移方程：

dp[i, v] 表示前 i 件物品放入容量为 v 的背包所能得到的最大价值。

dp[i, v] = max(dp[i - 1, v - k * C[i]] + k * W[i]) (0 ≤ k ≤ min(M[i], v / C[i]))

代码：

for (int i = 1; i <= N; i++) {
    for (int v = 0; v <= V; v++) {
        for (int k = 0; k <= min(v / C[i], M[i]); k++) {
            dp[i, v] = max(dp[i, v], dp[i - 1, v - k * C[i]] + k * W[i]);
        }
    }
}
return dp[N, V];

优化：

二进制！

将第 i 种物品拆分为 1，2，2²…2^{k - 1}，M_i - 2^k + 1 个物品的组合，然后使用 01 背包求解。

// 拆分
for (int i = 0; i < N; i++) {
    for (int k = 1; k <= M[i]; k *= 2) {
        new_C[new_N] = k * C[i];
        new_W[new_N] = k * W[i];
        M[i] -= k;
        new_N++;
    }
    if (M[i] > 0) {
        new_C[new_N] = M[i] * C[i];
        new_W[new_N] = M[i] * W[i];
        new_N++;
    }
}
// 01 背包
for (int i = 0; i < new_N; i++) {
    for (int v = V; v >= new_C[i]; v--) {
        dp[v] = max(dp[v], dp[v - new_C[i]] + new_W[i]);
    }
}
return dp[V];