一.01背包

• 问题背景：有$n$件物品和容量为$V$的背包，每件物品只能使用一次
• 第$i$件物品的体积是$v_i$，价值是$w_i$
• 求将哪些物品装入背包可以使总体积不超过背包容量，且总价值最大

1.分析

• 状态表示：f[i][j]表示只看前i个物品，总体积是j的情况下，所有方案的集合（属性：Max）
• 状态计算：
  1.不选第i个物品，f[i][j] = f[i - 1][j]
  2.选第i个物品，f[i][j] = f[i - 1][j - v[i]] + w[i]

2.对于初始化的一些思考

• 有时候题目会多一些限定条件，比如体积恰好为一个值的时候，最大价值是多少；或者是求方案数；或者是判断是否有可行的方案，我们应该具体情况具体分析
• 如果f[i][j]表示为体积不超过j的最大价值，则f应该全部初始化为0
f[0][j]表示一个物品都不选，体积不超过j的最大价值，所以都是合法方案，需要全部初始化为0
  最后求答案的时候，直接取f[n][v]
• 如果f[i][j]表示体积恰好为j时的最大价值，则f[0][0]应该初始化为0，其他都应该初始化为-INF
f[0][j]表示一件物品都不选，体积为j的最大价值，只有j=0时是合法方案，所以j不为0时应该全部初始化为-INF
  最后求答案的时候，取max(f[n][0], f[n][1],..., f[n][v])

3.代码模板

• 朴素版本

// 由于i-1需要被用到，所以物品下标需要从1开始，压缩空间后不需要
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= V; j++) {
        f[i][j] = f[i - 1][j];
        if (j >= v[i]) f[i][j] = Math.max(f[i][j], f[i - 1][j - v[i]] + w[i]);
    }
}

• 空间优化版(从后往前遍历)

for (int i = 0; i < n; i++) {
    for (int j = V; j >= v[i]; j--) {
        f[j] = Math.max(f[j], f[j - v[i]] + w[i]);
    }
}

二.完全背包

• 有$n$种物品和一个容量是$V$的背包，每种物品都有无限件可用。
• 第$i$种物品的体积是$v_i$，价值是$w_i$。
• 求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
  输出最大价值。

1.分析

• 状态表示：f[i][j]表示所有只从前i个物品中选，总体积不超过j的方案的集合（属性：Max）
• 状态计算：状态可以划分为对于第i个物品，选0个，选1个，…选k个
  1.f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i], f[i - 1][j - 2 * v[i]] + 2 * w[i],...)
  2.f[i][j - v[i]] = max(f[i - 1][j - v[i]], f[i - 1][j - 2 * v[i]] + w[i], f[i - 1][j - 3 * v[i]] + 2 * w[i], ...)
  3.由(1)(2)推出：f[i][j] = max(f[i - 1][j], f[i][j - v[i]] + w[i])

2.对比01背包和完全背包

• 01背包：f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i])
• 完全背包：f[i][j] = max(f[i - 1][j], f[i][j - v[i]] + w[i])
• 我们在把二维数组压缩成一维数组的时候，需要判断需要用到的状态是否已经被计算过，01背包如果压缩掉第一维，在计算f[j]的时候，f[j - v[i]]会被上一行的数据覆盖，所以需要逆向遍历数组来计算，而完全背包用的f[j - v[i]]就是本层的数据，可以直接正序遍历计算

3.代码模板

• 朴素版本

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

• 空间优化版

for (int i = 0; i < n; i++) {
    for (int j = v[i]; j <= V; j++) {
        f[j] = Math.max(f[j], f[j - v[i]] + w[i]);
    }
}

三.二维费用背包

• 有 $N$ 件物品和一个容量是 $V$ 的背包，背包能承受的最大重量是 $M$。
• 每件物品只能用一次。体积是 $v_i$，重量是 $m_i$，价值是 $w_i$。
• 将哪些物品装入背包，可使物品总体积不超过背包容量，总重量不超过背包可承受的最大重量，且价值总和最大

1.分析

• 状态表示：f[i][j][k]表示所有只从前i个物品中选，总体积不超过j的方案的集合，重量不超过k的最大价值（属性：Max）
• 状态转移：f[i][j][k] = max(f[i - 1][j][k], f[i - 1][j - v[i]][k - m[i]] + w[i])

2.思考

• 01背包和完全背包相当于模板，二维费用背包可以分别与两者进行结合，但代码的区别就是从前往后遍历和从后往前遍历费用的区别
• 区分三种问法：
  1. 体积最多是j：f全部初始化为0，且v >= 0
  2. 体积恰好是j：f[0]初始化为0，其他初始化为INF，正负取决于题目问最大还是最小，且v >= 0
  3. 体积最少是j：f[0]初始化为0，其他初始化为INF，正负取决于题目问最大还是最小，v < 0时状态也成立，只需要让v = 0即可

3.代码模板

int[][] f = new int[V + 1][M + 1];
for(int i = 0; i < N; i++){
    for(int j = V; j >= v[i]; j--){
        for(int k = M; k >= m[i]; k--){
            f[j][k] = Math.max(f[j][k], f[j - v[i]][k - m[i]] + w[i]);
        }
    }
}