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)