减小
增大
默认

护眼
夜间
默认

01背包问题

上一节
前面章节中，我们给您介绍了用贪心算法解决部分背包问题，本节我们讲解另一类背包问题——01背包问题。

仍以小偷在商店行窃为例，他随身携带的背包可以装一定重量的商品，商店中摆放着不同重量和价值的商品，小偷如何选择能获得最大的收益？在 01背包问题中，每种商品都是不可再分的，小偷在选择商品时，要么装入整个商品，要么放弃装该商品，不存在“装某商品的 1/2”的情况。

贪心算法仅适用于解决部分背包问题，不再适合解决 01背包问题。举个例子，假设商店摆放着以下几种商品：
  • 商品 1 ：重量为 6，收益为 6；
  • 商品 2 ：重量为 2，收益为 4；
  • 商品 3 ：重量为 3，收益为 4；
  • 商品 4 ：重量为 5，收益为 3。

假设背包可容纳商品的最大重量为 7，如果采用贪心算法，首先会选取收益最大的商品 1，此时背包的剩余承重为 1，无法再装下其他商品，因此最终获得的收益为 6。实际上还有一种更好的解决方案，即选择装入商品 2 和商品 3，总重量为 5（<7），总收益为 4 + 4 = 8。

显然，贪心算法不再适用于解决 01背包问题，解决此问题可以使用动态规划算法。

01背包问题的解决方案

假设背包可以承受的最大重量为 11，商店有 5 种商品，它们的重量和价值分别为：

wi 表示第 i 种商品的重量，vi 表示第 i 种商品的价值
w1 = 1，v1 = 1
w2 = 2，v2 = 6
w3 = 5，v3 = 18
w4 = 6，v4 = 22
w5 = 7，v5 = 28

采用动态规划算法解决此问题的具体过程是：

1) 从背包所能承受的最大重量为 1 开始，依次推导出各个承重条件下所能获得的最大收益。

建立如下这张表格，逐一分析出各个载重量下每一个商品装与不装对收益值的影响，从而获得各个载重量对应的最大收益值。

动态规划算法解决01背包问题
背包载重量 0 1 2 3 4 5 6 7 8 9 10 11
w1 = 1，v1 = 1 0                      
w2 = 2，v2 = 6 0                      
w3 = 5，v3 = 18 0                      
w4 = 6，v4 = 22 0                      
w5 = 7，v5 = 28 0                      

当背包载重量为 0 时，无法装入各个商品，因此收益一直为 0。


2) 首先考虑商品 (w1 , v1)，当背包载重量分别为 1、2、...、11 时，都可以装入此商品，且和不装该商品相比（背包是空的），装该商品的收益更大，因此对上表进行更新：

动态规划算法解决01背包问题
背包载重量 0 1 2 3 4 5 6 7 8 9 10 11
w1 = 1，v1 = 1 0 1 1 1 1 1 1 1 1 1 1 1
w2 = 2，v2 = 6 0                      
w3 = 5，v3 = 18 0                      
w4 = 6，v4 = 22 0                      
w5 = 7，v5 = 28 0                      

3) 再分析商品 (w2，v2)：
  • 载重量为 1 时：w2>1，无法装入该商品，最大收益仍为 1。
  • 载重量为 2 时：背包可以装入此商品，装入此商品对应的总收益可以用 6+f(0) 表示，其中 f(0) 指的是载重量为 0 时装 (w1,v1) 对应的最佳收益。从上表可知，f(0) = 0，因此 6+f(0)=6，比先前只装 (w1 , v1) 的收益大。
  • 载重量为 3 时：背包可以装入此商品，装入此商品对应的总收益可以用 6+f(1) 表示，f(1) 指的是载重量为 1 时装 (w1 , v1) 对应的最佳收益。从上表可知，f(1) = 1，因此 6+f(1) = 7，比先前只装 (w1 , v1) 的收益大。
  • 载重量为 4~11：背包可以装入此商品，且装此商品的收益总比不装时的大，总收益都为 7。 
 
继续对表格进行更新：

动态规划算法解决01背包问题
背包载重量 0 1 2 3 4 5 6 7 8 9 10 11
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                      
w4 = 6，v4 = 22 0                      
w5 = 7，v5 = 28 0                      

4) 再分析商品 (w3 , v3)：
  • 载重量为 1 时：w3>1，无法装入该商品，最大收益仍为 1。
  • 载重量为 2 时：w3>1，无法装入该商品，最大收益仍为 6。
  • 载重量为 3~4 时：w3>1，无法装入该商品，最大收益仍为 7。
  • 载重量为 5：背包可以装入此商品，且装此商品的总收益可以用 18+f(0) 表示，f(0) 指的是载重量为 0 时装 (w2 , v2) 对应的最佳收益。从上表可知，f(0) = 0，因此 18+f(0) = 18，比先前统计的收益值更高。
  • 载重量为 6：背包可以装入此商品，且装此商品的总收益可以用 18+f(1) 表示，f(1) 指的是载重量为 1 时装 (w2 , v2) 对应的最佳收益。从上表可知，f(1) = 1，因此 18+f(1) = 19，比先前统计的收益值更高。
  • 载重量为 7：背包可以装入此商品，且装此商品的总收益可以用 18+f(2) 表示，f(2) 指的是载重量为 2 时装 (w2 , v2) 对应的最佳收益。从上表可知，f(2) = 6，因此 18+f(2) = 24，比先前统计的收益值更高。
  • 根据此规律可以依次求得载重量分别为 8、9、...、11 时，对应的总收益为 25。

继续对表格进行更新：

动态规划算法解决01背包问题
背包载重量 0 1 2 3 4 5 6 7 8 9 10 11
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 0                      
w5 = 7，v5 = 28 0                      

5) 借助 (w3 , v3) 的收益数据，我们可以继续推导出不同载重量对应的 (w4 , v4) 商品的收益值；同理借助 (w4 , v4) 的收益数据，可以推导出不同载重量对应的 (w5 , v5) 商品的收益值。推导结果如下所示：

动态规划算法解决01背包问题
背包载重量 0 1 2 3 4 5 6 7 8 9 10 11
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 0 1 6 7 7 18 22 24 28 29 29 40
w5 = 7，v5 = 28 0 1 6 7 7 18 22 28 29 34 35 40

因此借助动态规划算法，当背包的载重量为 11 时，获得的最大收益为 40。

01背包问题的具体实现

如下的伪代码展示了动态规划算法解决 01背包问题的整个过程：

输入 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 背包问题的 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)

上一节