一. 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]);
    }
}

. 树形依赖