前面章节中,我们给您介绍了用贪心算法解决部分背包问题,本节我们讲解另一类背包问题——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)