完全背包问题（超级详细，附带源码）

通过阅读《01背包问题》一节，读者已经掌握了用动态规划的思想解决 01 背包问题。在此基础上，本节继续讲解完全背包问题的解决思路。

和 01 背包问题一样，完全背包问题也是从给定的物品中选择几样放入背包，使背包中物品的总收益最大。它们的区别在于，01 背包问题中每件物品只有 1 个，而完全背包问题中各个物品的数量是无限的，这意味着一样物品可以放入背包很多件。

完全背包问题也可以用动态规划的思想解决，接下来通过一个实例给大家做系统地讲解。

动态规划解决完全背包问题

虚拟一个场景，商店中拥有 5 种商品，它们各自的重量和收益分别是：

• 商品 1：重量 1 斤，收益 1 元；
• 商品 2：重量 2 斤，收益 6 元；
• 商品 3：重量 5 斤，收益 18 元；
• 商品 4：重量 6 斤，收益 22 元；
• 商品 5：重量 7 斤，收益 28 元。

假设背包的最大承重是 11 斤，各种商品的数量是无限的，如何选择才能实现背包的收益最大呢？

动态规划解决这个问题的思路是：从第一件商品（商品 1）开始，尝试将各个商品装入承重为 1~11 的背包里，时刻保证背包里的收益是最大的。为了方便大家理解，下面制作了一张表格：

表1：动态规划算法解决完全背包问题

商品种类	背包承重
	0	1	2	3	4	5	6	7	8	9	10	11
不装任何商品	0	0	0	0	0	0	0	0	0	0	0	0
w1 = 1，v1 = 1
w2 = 2，v2 = 6
w3 = 5，v3 = 18
w4 = 6，v4 = 22
w5 = 7，v5 = 28

wi 表示第 i 件商品的重量，vi 表示第 i 件商品的收益值。

显然，在不装任何商品的情况下，各种容量的背包里都是空的，收益都是 0。

1) 考虑将商品 w1 装入各个背包：

• 承重为 0 的背包：无法装 w1，此时背包的收益仍为不装任何商品时的收益；
• 承重为 1 的背包：可以装 w1，与不装任何商品时的收益相比，装入 w1 后的收益增加了，新的收益值为 1；
• 承重为 2 的背包：可以装 w1，与不装任何商品时的收益相比，装入 w1 后的收益增加了。当前背包的承重是 2 斤，w1 商品的重量是 1 斤，因此 w1 的收益值加上承重为 1 的背包的最大收益值，就是当前背包的收益值，结果是 2（1+1）；
• 承重为 3 的背包：可以装 w1，与不装任何商品时的收益相比，装入 w1 后的收益增加了。当前背包的承重是 3 斤，w1 商品的重量是 1 斤，因此 w1 的收益值加上承重为 2 的背包的最大收益值，就是当前背包的收益值，结果是 3（1+2）；
• ......
• 承重为 11 的背包：可以装 w1，与不装任何商品时的收益相比，装入 w1 后的收益增加了。当前背包的承重是 11 斤，w1 商品的重量是 1 斤，因此 w1 的收益值加上承重为 10 的背包的最大收益值，就是当前背包的收益值，结果是 11（1+10）；

更新表 1，最新的表格如下：

表2：动态规划算法解决完全背包问题

商品种类	背包承重
	0	1	2	3	4	5	6	7	8	9	10	11
不装任何商品	0	0	0	0	0	0	0	0	0	0	0	0
w1 = 1，v1 = 1	0	1	2	3	4	5	6	7	8	9	10	11
w2 = 2，v2 = 6
w3 = 5，v3 = 18
w4 = 6，v4 = 22
w5 = 7，v5 = 28

用 f(n) 表示承重值为 n 的背包对应的最大收益。从算法的角度，各个背包的收益值是：f(1)=1+f(0)、f(2)=1+f(1)、...、f(11)=1+f(10)，其中 1 指的是 w1 的收益值，f(0)~f(10) 指的是承重分别为 0~10 的背包的最大收益值。

2) 考虑将商品 w2 装入各个背包：

• 承重为 0 的背包：无法装 w2，此时背包的收益仍为不装任何商品时的收益 0；
• 承重为 1 的背包：无法装 w2，此时背包的收益仍为只考虑 w1 时的最大收益，也就是 1；
• 承重为 2 的背包：可以装 w2，与之前选择 w1 时的收益值 2 相比，装 w2 的收益值是：6 + 0 (承重为 0 的背包的最大收益值) = 6，6 > 2，显然后者的收益更大；
• 承重为 3 的背包：可以装 w2，与之前选择 w1 时的收益值 3 相比，装 w2 的收益值是：6 + 1 (承重为 1 的背包的最大收益值) = 7，7 > 3，显然后者的收益更大；
• 承重为 4 的背包：可以装 w2，与之前选择 w1 时的收益值 4 相比，装 w2 的收益值是：6 + 6 (承重为 2 的背包的最大收益值) = 12，12 > 4，显然后者的收益更大；
• ......
• 承重为 11 的背包：可以装 w2，与之前选择 w1 时的收益值 11 相比，装 w2 的收益值是：11 +  (承重为 9 的背包的最大收益值) = 12，12 > 4，显然后者的收益更大；

更新后的表格如下：

表3：动态规划算法解决完全背包问题

商品种类	背包承重
	0	1	2	3	4	5	6	7	8	9	10	11
不装任何商品	0	0	0	0	0	0	0	0	0	0	0	0
w1 = 1，v1 = 1	0	1	2	3	4	5	6	7	8	9	10	11
w2 = 2，v2 = 6	0	1	6	7	12	13	18	19	24	25	30	31
w3 = 5，v3 = 18
w4 = 6，v4 = 22
w5 = 7，v5 = 28

f(0) 和 f(1) 不变，f(2)=6+f(0)、f(3)=6+f(1)...、f(11)=6+f(9)，其中 6 指的是 w2 的收益值，f(0)~f(9) 指的是承重分别为 0~9 的背包的最大收益值。

3) 考虑将商品 w3 装入各个背包，它们的最大收益分别是：

• f(0) = 0
• f(1) = 1
• f(2) = 6
• f(3) = 7
• f(4) = 12
• f(5) = 18+f(0) = 18，比之前的 12 大，所以选择 18；
• f(6) = 18+f(1) = 19，比之前的 18 大，所以选择 19；
• f(7) = 18+f(2) = 24，比之前的 19 大，所以选择 24；
• f(8) = 18+f(3) = 25，比之前的 24 大，所以选择 25；
• f(9) = 18+f(4) = 30，比之前的 25 大，所以选择 30；
• f(10) = 18+f(5) = 36，比之前的 30 大，所以选择 36；
• f(11) = 18+f(8) = 43，比之前的 31 大，所以选择 43。

更新后的表格如下：

表4：动态规划算法解决完全背包问题

商品种类	背包承重
	0	1	2	3	4	5	6	7	8	9	10	11
不装任何商品	0	0	0	0	0	0	0	0	0	0	0	0
w1 = 1，v1 = 1	0	1	2	3	4	5	6	7	8	9	10	11
w2 = 2，v2 = 6	0	1	6	7	12	13	18	19	24	25	30	31
w3 = 5，v3 = 18	0	1	6	7	12	18	19	24	25	30	36	37
w4 = 6，v4 = 22
w5 = 7，v5 = 28

以此类推，选择将 w4、w5 装入背包，把表格填写完整：

表5：动态规划算法解决完全背包问题

商品种类	背包承重
	0	1	2	3	4	5	6	7	8	9	10	11
不装任何商品	0	0	0	0	0	0	0	0	0	0	0	0
w1 = 1，v1 = 1	0	1	2	3	4	5	6	7	8	9	10	11
w2 = 2，v2 = 6	0	1	6	7	12	13	18	19	24	25	30	31
w3 = 5，v3 = 18	0	1	6	7	12	18	19	24	25	30	36	37
w4 = 6，v4 = 22	0	1	6	7	12	18	22	24	28	30	36	40
w5 = 7，v5 = 28	0	1	6	7	12	18	22	28	29	34	36	40

 
由此，背包能承载的最大重量是 11 斤，能装入的最大收益是 40 元。下面以伪代码的形式给大家总结了推理的整个过程：

输入 N    // 指定商品种类
输入 W    // 指定背包载重量
//w[] 记录各个商品的载重量，v[] 记录各个商品对应的收益
knapsack(w[] , v[]):
    //逐个遍历每个商品
    for i <- 1 to N：
        //求出从 1 到 W 各个载重量对应的最大收益
        for j <- 1 to W:
            //如果背包载重量小于商品总重量，则商品无法放入背包，收益不变
            if  j < w[i]:
                result[i][j] <- result[i-1][j]
            else:
                //比较装入该商品（装多个）和不装该商品，哪种情况获得的收益更大，记录最大收益值
                result[i][j] <- max(result[i-1][j] , v[i]+result[i][j-w[i]])
    return result 

对比表 5 和《01背包问题》一节的表格，观察每一行数据在计算方式上的差异，能够轻松看出 01 背包和完全背包的区别。

完全背包问题的具体实现

结合伪代码，下面是用动态规划算法解决完全背包问题的 C 语言程序：

#include<stdio.h>
#define N 5    //商品的种类
#define W 11   //背包的最大承重
/*
动态规划算法解决完全背包问题
result[N + 1][W + 1]：存储最终的结果
w[N + 1]：存储各商品的重量
v[N + 1]：存储各商品的价值
*/
void knapsack(int result[N + 1][W + 1], int w[N + 1], int v[N + 1]) {
    int i, j;
    //逐个遍历每个商品
    for (i = 1; i <= N; i++) {
        //求出从 1 到 W 各个载重对应的最大收益
        for (j = 1; j <= W; j++) {
            //如果背包载重小于商品总重量，则该商品无法放入背包，收益不变
            if (j < w[i])
                result[i][j] = result[i - 1][j];
            else
                //比较装入该商品和不装该商品，哪种情况获得的收益更大，记录最大收益值
                result[i][j] = result[i-1][j] > (v[i] + result[i][j - w[i]]) ? result[i - 1][j] : (v[i] + result[i][j - w[i]]);
        }
    }
}

int main()
{
    int w[N + 1] = { 0,1 , 2 , 5 , 6 , 7 };           //商品的承重
    int v[N + 1] = { 0,1 , 6 , 18 , 22 , 28 };        //商品的价值
    int result[N + 1][W + 1] = { 0 };                 //记录统计数据
    knapsack(result, w, v);
    printf("背包承重为 %d, 最大收益为 %d\n", W, result[N][W]);
    return 0;
}

如下为用动态规划算法解决完全背包问题的 Java 程序：

public class Knapsack {
    static final int N = 5;  // 商品的种类
    static final int W = 11; // 背包的最大承重

    // 动态规划算法解决完全背包问题
    public static void knapsack(int[][] result, int[] w, int[] v) {
        // 逐个遍历每个商品
        for (int i = 1; i <= N; i++) {
            // 求出从 1 到 W 各个载重对应的最大收益
            for (int j = 1; j <= W; j++) {
                // 如果背包载重小于商品总重量，则该商品无法放入背包，收益不变
                if (j < w[i])
                    result[i][j] = result[i - 1][j];
                else
                    // 比较装入该商品和不装该商品，哪种情况获得的收益更大，记录最大收益值
                    result[i][j] = Math.max(result[i - 1][j], v[i] + result[i][j - w[i]]);
            }
        }
    }

    public static void main(String[] args) {
        int[] w = {0, 1, 2, 5, 6, 7};      // 商品的承重
        int[] v = {0, 1, 6, 18, 22, 28};   // 商品的价值
        int[][] result = new int[N + 1][W + 1]; // 记录统计数据

        knapsack(result, w, v);
        System.out.println("背包承重为 " + W + ", 最大收益为 " + result[N][W]);
    }
}

如下为用动态规划算法解决完全背包问题的 Python 程序：

def knapsack(W, w, v):
    N = len(w) - 1  # 商品种类
    result = [[0 for _ in range(W + 1)] for _ in range(N + 1)]

    # 遍历每个商品
    for i in range(1, N + 1):
        # 求出不同载重下的最大收益
        for j in range(1, W + 1):
            if j < w[i]:
                result[i][j] = result[i - 1][j]
            else:
                result[i][j] = max(result[i - 1][j], v[i] + result[i][j - w[i]])

    return result[N][W]

# 商品的重量和价值
w = [0, 1, 2, 5, 6, 7]
v = [0, 1, 6, 18, 22, 28]

# 背包最大承重
W = 11

# 计算最大收益
max_profit = knapsack(W, w, v)
print(f"背包承重为 {W}, 最大收益为 {max_profit}")

运行程序，输出结果为：

背包承重为 11, 最大收益为 40