查看“︁12-动态规划/03-背包DP”︁的源代码


== 背包问题 ==

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

== 01 背包 ==

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

<syntaxhighlight lang="cpp">
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]);
</syntaxhighlight>

== 完全背包 ==

每个物品可选无限次。

<syntaxhighlight lang="cpp">
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]);
</syntaxhighlight>

== 多重背包 ==

每个物品有 <math>k_i</math> 个。可用'''二进制拆分'''优化：

<syntaxhighlight lang="cpp">
// 将 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]);
    }
}
</syntaxhighlight>

== 分组背包 ==

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

<syntaxhighlight lang="cpp">
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]);
</syntaxhighlight>

[[Category:动态规划]]
[[Category:三三文档]]