首页 > 编程笔记

01背包问题

商店的货架上摆放着不同重量和价值的商品，一个小偷在商店行窃，他携带的背包只能装固定重量的商品。装哪些商品才能获得最大的收益呢？在限定条件内找到最佳的物品组合，这样的问题统称为背包问题。

根据限定的条件不同，背包问题还可以细分：

部分背包问题：所有物品是可再分的，即允许将某件物品的一部分（例如 1/3）放入背包；
0-1 背包问题：所有物品不可再分，要么整个装入背包，要么放弃，不允许出现“仅选择物品的 1/3 装入背包”的情况；
完全背包问题：不对每一件物品的数量做限制，同一件物品可以选择多个装入背包；
多重背包问题：每件物品的数量是有严格规定的，比如物品 A 有 2 件，物品 B 有 3 件。

前面章节中，我们学会了用贪心算法解决部分背包问题。本节，我们学习如何用动态规划算法解决 0-1 背包问题。

动态规划解决01背包问题

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

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

所有商品不可再分，顾客要么“整件”购买商品，要么放弃购买。一个小偷想窃取商品，他的背包只能装 11 斤商品，如何选择商品才能获得最大的收益呢？

动态规划算法解决此问题的核心思想是：背包承重 1 斤时所能获得的最大收益是很容易计算的，在此基础上，可以推算出背包承重 2 斤、3斤、...、14斤、15斤时所能获得的最大收益。建立如下这张表格，依次将各个商品装入不同承重的背包中，计算出它们所能获得的最大收益。

表 1 动态规划算法解决01背包问题
商品种类	背包承重
商品种类	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) 首先考虑将商品一装入各个背包，除了承重值为 0 的背包，其它背包都能装入，且与不装任何商品相比，装入商品一后各个背包的收益更大，各个背包的收益值如表 2 所示：

表 2 动态规划算法解决01背包问题
商品种类	背包承重
商品种类	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	1	1	1	1	1	1	1	1	1	1
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 指的是商品一的收益值，f(0)~f(10) 指的是不装任何商品时承重分别为 0~10 的背包对应的收益值，借助表格可以看到，它们的值都为 0。

2) 考虑将商品二装入各个背包，除了承重值为 0 和 1 的背包，其它背包都可以装入。我们可以计算出它们各自对应的收益值：

f(2) = 6 + f(0) = 6
f(3) = 6 + f(1) = 7
f(4) = 6 + f(2) = 7
...
f(9) = 6 + f(7) = 7
f(10) = 6 + f(8) = 7
f(11) = 6 + f(9) = 7

等号右侧 f(0)~f(9) 的值是表 2 中装入商品一的各个背包对应的收益值。相比装入商品一统计的各个背包的收益值，装入商品二能使提高各个背包的收益。更新后的表格为：

表 3 动态规划算法解决01背包问题
商品种类	背包承重
商品种类	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	1	1	1	1	1	1	1	1	1	1
w2 = 2，v2 = 6	0	1	6	7	7	7	7	7	7	7	7	7
w3 = 5，v3 = 18
w4 = 6，v4 = 22
w5 = 7，v5 = 28

3) 考虑将商品三装入各个背包，除了承重值为小于 5 的背包，其它背包都可以装入。我们可以计算出它们各自对应的收益值：

f(5) = 18 + f(0) = 18
f(6) = 18 + f(1) = 19
f(7) = 18 + f(2) = 24
f(8) = 18 + f(3) = 25
f(9) = 18 + f(4) = 25
f(10) = 18 + f(5) = 25
f(11) = 18 + f(6) = 25

等号右侧 f(0)~f(6) 的值是表 2 中装入商品二的各个背包对应的收益值。和装入商品二时统计的各个背包的收益值相比，装入商品三能提高各个背包的收益。更新后的表格为：

表 4 动态规划算法解决01背包问题
商品种类	背包承重
商品种类	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	1	1	1	1	1	1	1	1	1	1
w2 = 2，v2 = 6	0	1	6	7	7	7	7	7	7	7	7	7
w3 = 5，v3 = 18	0	1	6	7	7	18	19	24	25	25	25	25
w4 = 6，v4 = 22
w5 = 7，v5 = 28

4) 采用同样的方法，我们可以将表 4 中缺失的数据补全，最终得到的表格为：

表 5 动态规划算法解决01背包问题
商品种类
商品种类	1	2	3	4	5	6	7	8	9	10	11
不装任何商品	0	0	0	0	0	0	0	0	0	0	0
w1 = 1，v1 = 1	1	1	1	1	1	1	1	1	1	1	1
w2 = 2，v2 = 6	1	6	7	7	7	7	7	7	7	7	7
w3 = 5，v3 = 18	1	6	7	7	18	19	24	25	25	25	25
w4 = 6，v4 = 22	1	6	7	7	18	22	24	28	29	29	40
w5 = 7，v5 = 28	1	6	7	7	18	22	28	29	34	35	40

注意，并不是每试图装入一个新商品，背包的收益一定会提高。举个例子，承重为 7 斤的背包装入商品四时的最大收益是：f(7) = 22+f(1) = 23，装入商品三时最大的收益值为：f(7) = 18+f(2) = 24。因此，表 5 中承重 7 斤的背包装入商品 4 时对应的收益值仍为 24，并未发生改变。

结合表 5，当背包承重为 11 斤时，所能获得的最大收益为 40 元。如下以伪代码的形式给大家总结了以上推理的整个过程：

输入 N    // 指定商品种类
输入 W    // 指定背包载重量
//w[] 记录各个商品的载重量，v[] 记录各个商品对应的收益
knapsack01(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-1][j-w[i]])
    return result

01背包问题的具体实现

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

#include<stdio.h>
#define N 5    //商品的种类
#define W 11   //背包的最大承重
/*
动态规划算法解决01背包问题
result[N + 1][W + 1]：存储最终的结果
w[N + 1]：存储各商品的重量
v[N + 1]：存储各商品的价值
*/
void knapsack01(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 - 1][j - w[i]]) ? result[i - 1][j] : (v[i] + result[i - 1][j - w[i]]);
        }
    }
}
//追溯选中的商品
void select(int result[N + 1][W + 1], int w[N + 1], int v[N + 1]) {
    int n = N;
    int bagw = W;
    //逐个商品进行判断
    while (n > 0) {
        //如果在指定载重量下，该商品对应的收益和上一个商品对应的收益相同，则表明未选中
        if (result[n][bagw] == result[n - 1][bagw]) {
            n--;
        }
        else {
            //输出被选用商品的重量和价值
            printf("(%d,%d) ", w[n], v[n]);
            //删除被选用商品的承重，以便继续遍历
            bagw = bagw - w[n];
            n--;
        }
    }
}

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 };                        //记录统计数据
    knapsack01(result, w, v);
    printf("背包承重为 %d,最大收益为 %d\n", W, result[N][W]);
    printf("选择了：");
    select(result, w, v);
    return 0;
}

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

public class Demo {
    static int N = 5;//商品的种类
    static int W = 11;//背包的承重
    //动态规划算法解决01背包问题
    public static void knapsack01(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] = result[i - 1][j] > (v[i] + result[i - 1][j - w[i]]) ? result[i - 1][j] : (v[i] + result[i - 1][j - w[i]]);
                }
            }
        }
    }
    //追溯选中的商品
    public static void select(int [][] result , int [] w,int []v) {
        int n = N;
        int bagw = W;
        //逐个商品进行判断
        while(n>0) {
            //如果在指定承重下，该商品对应的收益和上一个商品对应的收益相同，则表明未选中
             if (result[n][bagw] == result[n - 1][bagw]) {
                    n--;
                }
                else {
                    //输出被选用商品的重量和价值
                    System.out.print("("+w[n]+","+v[n]+") ");
                    //删除被选用商品的承重，以便继续遍历
                    bagw = bagw - w[n];
                    n--;
                }
        }
    }
    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];
        knapsack01(result, w, v);;
        System.out.println("背包可容纳重量为 "+W+"，最大收益为 "+result[N][W]);
        System.out.print("选择了");
        select(result, w,v);
    }
}

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

N = 5       #商品的种类
W = 11      #背包的承重
w = [0,1,2,5,6,7]    #商品的承重，不使用 w[0]
v = [0,1,6,18,22,28]   #商品的价值，不使用 v[0]
#二维列表，记录统计数据
result = [[0]*(W+1),[0]*(W+1),[0]*(W+1),[0]*(W+1),[0]*(W+1),[0]*(W+1)]
#动态规划算法解决01背包问题
def knapsack01():
    #逐个遍历每个商品
    for i in range(1,N+1):
        #求出从 1 到 W 各个承重对应的最大收益
        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-1][j-w[i]])

knapsack01()
print("背包可容纳重量为 %d,最大收益为 %d"%(W, result[N][W]))
#追溯选中的商品
def select():
    n = N
    bagw = W
    #逐个商品进行判断
    while n > 0:
         #如果在指定承重下，该商品对应的收益和上一个商品对应的收益相同，则表明未选中
        if result[n][bagw] == result[n-1][bagw]:
            n = n - 1
        else:
            #输出被选用商品的重量和价值
            print("(%d,%d) "%(w[n],v[n]))
            #删除被选用商品的承重，以便继续遍历
            bagw = bagw - w[n]
            n = n - 1

print("所选商品为:")
select()

以上程序的输出结果均为：

背包可容纳重量为 11，最大收益为 40
选择了(6,22) (5,18)

01背包问题

动态规划解决01背包问题

01背包问题的具体实现

推荐阅读