笔记 – 各种背包问题

一. 01背包

01背包问题关键在于某个物品取还是不取，状态可以从上一个占用空间转移而来。

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

二. 完全背包

完全背包问题就是一个物品可以无限次取。那么我们可以正序推背包空间，这样在下一次取 i 号物品的时候上一次是取过 i 号物品的。

for(int i = 1; i <= n; i++) {
    for(int j = c[i]; i <= m; j++) {
        dp[j] = max(dp[j], dp[j - c[i]] + w[i]);
    }
}

三. 分组背包

分组背包就是一些物品分成了 n 组，每组只能选一个物品。c_{i,k} 表示第i组第k个物品的体积，价值为 w_{i,k}。
可以定义 dp_{i,j} 为前 i 组物品装进容量 j 的背包的最大价值。

for(int i = 1; i <= n; i++) {
    for(int j = m; j >= 0; j--) {
        for(int k = 1; k <= m; k++) {
            if(j >= c[i][k]) {
                dp[j] = max(dp[j], dp[j - c[i][k]] + w[i][k]);
            }
        }
    }
}

四. 多重背包

多重背包问题有 n 种物品，体积为 c_i ，价值为 w_i ，有 m_i 个。
我们当然可以将问题转化成01背包或者直接枚举 0-k 个物品。（但是注意这个不能像完全背包一样，因为你无法统计物品的数量）

• 朴素算法

添加一层循环枚举个数，直至个数上限。而每个位置都需枚举，则复杂度乘以m。状态同样可以压缩一维。

• 二进制拆分优化

可以将m个物品用二进制拆成多种物品，例如一种有25个的物品，可以用二进制拆成 25 = 1+2+4+8+10个。这样可以构成1至25的个数的所有方案。

一开始就可以将这些物品拆出来，时空复杂度都乘以log_m。

int new_n = 0;
for(int i = 1; i <= n; i++) {
    for(int j = 1; j <= m[i]; j <<= 1) {
        m[i] -= j;
        new_c[++new_n] = j * c[i];//原始参数可以不用数组存储，只利用一次，节省空间
        new_w[new_n] = j * w[i];
    }
    if(m[i]) {
        new_c[++new_n] = m[i] * c[i];
        mew_w[new_n] = m[i] * w[i];
    }
}

• 单调队列优化

五. 满背包方案数

这是将背包恰好装满的方案数问题。
事实上，这是一个关于方案数的递推问题，顺序枚举，观察枚举到的容量与当前的w_i的关系。

  for(int i = 1; i <= n; i++) {
    for(int j = 1; j <= m; j++) {
      if(j == w[i]) dp[i][j] = dp[i - 1][j] + 1;//如果钱刚好够，方案数加1，因为是全新的方案
      if(j < w[i]) dp[i][j] = dp[i - 1][j];//如果钱不够，方案数不加，但是要继承一下，因为这个钱对应的方案数不会变
      if(j > w[i]) dp[i][j] = dp[i - 1][j] + dp[i - 1][j - w[i]];//如果钱太多了，在之前的基础上会有另一个数值的方案数
    }
  }

六. 最小剩余空间

求出背包占用的最大空间，不求价值。这个时候我们把dp时累加上的权值换成体积就可以了。

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

. 树形依赖