首页 > 算法 阅读:8,078

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) = 1
f(3) = 6 + f(1) = 6
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背包问题
商品种类 背包承重
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 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

注意,并不是每试图装入一个新商品,背包的收益一定会提高。举个例子,承重为 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)

关注公众号「站长严长生」,在手机上阅读所有教程,随时随地都能学习。本公众号由站长亲自运营,长期更新,坚持原创,专注于分享创业故事+学习历程+工作记录+生活日常+编程资料。

公众号二维码
微信扫码关注公众号