背包问题

01背包

• 01背包每种物品只有1件
• 你要吗装，要么不装

理解

• 装：1
• 不装：0

算法流程

• 数组定义：

• dp[i][j] : 前i钟物品在背包容量为j时装的最大价值
  

• 转移方程：

• 对于第i件物品有两种情况：
      vi表示第i件物品的体积或重量，wi表示价值
      情况1：背包容量足够大j >= vi，可以装第i件物品：
          装：dp[i][j] = dp[i - 1][j - vi] + wi;
          不装：dp[i][j] = dp[i - 1][j];
          故：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - vi] + wi);
      情况2：背包容量不够大 j < vi，装不了：dp[i][j] = dp[i - 1][j];
  

• 初始化：

• memset(dp, 0, sizeof(dp));
  

代码演示朴素版

for (int i = 1; i <= n; i++) {
    for (int j = 1; 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];
        }
    }
}

代码演示二：空间优化

• 思路：由0-1背包的状态转移方程dp[i] [j] = max{dp[i - 1] [j]，dp[i - 1] [j-v[i] ]+w[i]}

• dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i]);
  

• 的特点，知道当前状态仅依赖前一状态的剩余容量与当前物品重量v[i]的关系。

• 根据这个特点，我们可以将dp降到一维即dp[j] = max{dp[j]，dp[j-w[i]]+v[i]}。从这个方程中我们可以发现，有两个dp[j]，但是要区分开。

• 等号左边的j是当前i的状态，右边括号中的j是第i-1状态下的值。

• 保证 dp[j - vi] 未在此轮计算过, 即 dp[j - vi]依然属于 i-1 行

• 如果j从0到V遍历，那么更新到 j 时，dp[j - vi]已经更新过了，变为第i行的dp[j - vi]，不再是第i - 1行的 dp[j - vi]

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

解释：V为背包最大（容量或体积或承重量），dp[j] 表示背包容量为j时的最大价值

完全背包

• 每种物品数量没有限制
• 一种物品你可以重复装，无限制

算法流程

• 数组定义：

• dp[i][j] : 前i钟物品在背包容量为j时装的最大价值
  

• 转移方程：

• 对于第i件物品有两种情况：
      vi表示第i件物品的体积或重量，wi表示价值
      情况1：背包容量足够大j >= vi，可以装第i件物品：
          装：dp[i][j] = dp[i - 1][j - vi] + wi;
          不装：dp[i][j] = dp[i - 1][j];
          故：dp[i][j] = max(dp[i - 1][j], dp[i][j - vi] + wi);
      情况2：背包容量不够大 j < vi，装不了：dp[i][j] = dp[i - 1][j];
  

• 初始化：

• memset(dp, 0, sizeof(dp));
  

重点

• 对于前i种物品，我们可以装多件该物品，则转移方程为：

• dp[i][j] = max(dp[i - 1][j], dp[i][j - vi] + wi);
  

代码实现

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

空间优化

• 对当前dp[i] [j]，只与当前行也就是dp[i] [j - vi]（加）和dp[i - 1] [j]（不加）有关
• 故需要知道dp[i] [j - vi]，则j从0到V

代码演示

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

多重背包

• 每种物品数量有限制
• 一种物品i你可以重复装，至多可以装si件
• 多重背包是介于01背包和完全背包之间，更贴切现实生活

转化

多重背包转化为01背包

代码演示

#define MAX_V 100005

int dp[MAX_V];

int v[101], s[101], w[101];
int V, n;
void duochongbeibao() {

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= s[i]; j++) { //当成01背包，相同物品当作不同物品循环 
            for (int vv = V; vv; vv--) {
                if (vv >= j * v[i]) {
                    dp[vv] = max(dp[vv], dp[vv - v[i]] + w[i]);
                }
            }
        } 
    }
    printf("%d\n", dp[V]);
    return ;
}

速度太慢了

二进制拆分优化

• 对于上面代码，我们是循环遍历每个si，效率太慢

• 例如对于si = 71

• 那么si = 1 + 2 + 4 + 8 + 16 + 32 + 8

代码演示

for (int i = 1; i <= n; i++) {
    for (int k = 1; s[i]; s[i] -= k, k <<= 1) { //当成01背包，相同物品当作不同物品循环 
        k = min(k, s[i]);
        //printf("%d %d\n", k, s[i]);
        for (int j = V; j >= k * v[i]; j--) {
            dp[j] = max(dp[j], dp[j - k * v[i]] + k * w[i]);
        }
    } 
}

空间优化

for (int i = 1; i <= n; i++) {
    int s, w, v;
    scanf("%d %d %d", &s, &v, &w);
    for (int k = 1; s; s -= k, k <<= 1) { //当成01背包，二进制拆分
        k = min(k, s);
        //printf("%d %d\n", k, s);
        for (int j = V; j >= k * v; j--) {
            dp[j] = max(dp[j], dp[j - k * v] + k * w);
        }
    } 
}

单调队列优化

• 最快的多重背包做法

时间复杂度：O(nV)