12-动态规划/03-背包DP

背包问题

背包问题是一类经典的 DP 问题：给定 [math]\displaystyle{ n }[/math] 个物品，每个物品有体积（重量）[math]\displaystyle{ w_i }[/math] 和价值 [math]\displaystyle{ v_i }[/math]，在总容量不超过 [math]\displaystyle{ W }[/math] 的前提下，求最大总价值。

01 背包

每个物品只能选或不选（0 或 1 次）。

int dp[MAXW]; // 一维优化，dp[j] = 容量 j 的最大价值
memset(dp, 0, sizeof dp);

for (int i = 1; i <= n; i++)
    for (int j = W; j >= w[i]; j--) // 倒序：防止同一物品被多次使用
        dp[j] = max(dp[j], dp[j - w[i]] + v[i]);

完全背包

每个物品可选无限次。

for (int i = 1; i <= n; i++)
    for (int j = w[i]; j <= W; j++) // 正序：允许同一物品多次使用
        dp[j] = max(dp[j], dp[j - w[i]] + v[i]);

多重背包

每个物品有 [math]\displaystyle{ k_i }[/math] 个。可用二进制拆分优化：

// 将 k 个物品拆成 logs 组：1, 2, 4, ..., 剩余
for (int i = 1; i <= n; i++)
{
    int k = cnt[i]; // 该物品的个数
    for (int t = 1; t <= k; t <<= 1)
    {
        k -= t;
        // 把 t 个物品视为一个"新物品"，做 01 背包
        for (int j = W; j >= t * w[i]; j--)
            dp[j] = max(dp[j], dp[j - t * w[i]] + t * v[i]);
    }
    if (k)
    {
        for (int j = W; j >= k * w[i]; j--)
            dp[j] = max(dp[j], dp[j - k * w[i]] + k * v[i]);
    }
}

分组背包

物品分成若干组，每组最多选一个：

for (int grp = 1; grp <= g; grp++)
    for (int j = W; j >= 0; j--) // 倒序
        for (int i : group[grp])
            if (j >= w[i])
                dp[j] = max(dp[j], dp[j - w[i]] + v[i]);