背包问题

字数统计: 3.5k   |   阅读时长≈ 16 分钟

背包问题是一类经典的动态规划问题

问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。NPC问题是没有多项式时间复杂度的解法的，但是利用动态规划，我们可以以伪多项式时间复杂度求解背包问题。

一般来讲，背包问题分为以下几类：

  • 01背包问题；
  • 完全背包问题；
  • 多重背包问题；

先说明01背包问题。

1. 01背包问题

1.1 题目

01背包问题（01 knapsack problem）：一共有N件物品，第i（i从1开始）件物品的重量为w[i]，价值为v[i]。在总重量不超过背包承载上限W的情况下，能够装入背包的最大价值是多少？

1.2 分析

书包内物品的总价值，而变量是物品和书包的限重，所以我们可定义状态dp:

1
dp[i][j]表示将前i件物品装进限重为j的背包可以获得的最大价值, 0<=i<=N, 0<=j<=W

解决办法：

给定 c 种物品和一个容量为 d 的背包，物品 i 的重量是 w[i]，其价值为 v[i]。

声明一个 大小为 m[c] [d] 的二维数组，m[ i ] [ j ] 表示 在面对第 i 件物品，且背包容量为 j 时所能获得的最大价值 ，那么我们可以很容易分析得出 m[i] [j] 的计算方法。

  1. j < w[i] 的情况，这时候背包容量不足以放下第 i 件物品，只能选择不拿，最大价值入参为： m[ i ] [ j ] = m[ i-1 ] [ j ]

  2. j>=w[i] 的情况，这时背包容量可以放下第 i 件物品，我们就要考虑拿这件物品是否能获取更大的价值。

如果拿取，m[ i ] [ j ]=m[ i-1 ] [ j-w[ i ] ] + v[ i ]。 这里的m[ i-1 ] [ j-w[ i ] ]指的就是考虑了i-1件物品，背包容量为j-w[i]时的最大价值，也是相当于为第i件物品腾出了w[i]的空间。

如果不拿，m[ i ] [ j ] = m[ i-1 ] [ j ] , 同1所述。

究竟是拿还是不拿，自然是比较这两种情况那种价值最大。

由此可以得到状态转移方程

1
2
3
4
if(j>=w[i])
    m[i][j]=max(m[i-1][j],m[i-1][j-w[i]]+v[i]);
else
    m[i][j]=m[i-1][j];

1.3 背包问题解决过程

问题描述

有n个物品，它们有各自的体积和价值，现有给定容量的背包，如何让背包里装入的物品具有最大的价值总和

为方便讲解和理解，下面讲述的例子均先用具体的数字代入，即：eg：number＝4，capacity＝8

i（物品编号） 1 2 3 4
w（体积） 2 3 4 5
v（价值） 3 4 5 6

在解决问题之前，为描述方便，首先定义一些变量：Vi表示第 i 个物品的价值，Wi表示第 i 个物品的体积，定义V(i,j)：当前背包容量 j，前 i 个物品最佳组合对应的价值，同时背包问题抽象化（X1，X2，…，Xn，其中 Xi 取0或1，表示第 i 个物品选或不选）。

  1. 建立模型，即求max(V1X1+V2X2+…+VnXn)；
  2. 寻找约束条件，W1X1+W2X2+…+WnXn < capacity；
  3. 寻找递推关系式，面对当前商品有两种可能性：
  • 包的容量比该商品体积小，装不下，此时的价值与前i-1个的价值是一样的，即V(i,j)=V(i-1,j)；
  • 还有足够的容量可以装该商品，但装了也不一定达到当前最优价值，所以在装与不装之间选择最优的一个，即V(i,j)=max｛V(i-1,j)，V(i-1,j-w(i))+v(i)｝。

其中V(i-1,j)表示不装，V(i-1,j-w(i))+v(i) 表示装了第i个商品，背包容量减少w(i)，但价值增加了v(i)；

由此可以得出递推关系式：

  • j < w(i) V(i,j)=V(i-1,j)
  • j >= w(i) V(i,j)=max｛V(i-1,j)，V(i-1,j-w(i))+v(i)｝

这里需要解释一下，为什么能装的情况下，需要这样求解（这才是本问题的关键所在！）：

可以这么理解，如果要到达V(i,j)这一个状态有几种方式？

肯定是两种，第一种是第i件商品没有装进去，第二种是第i件商品装进去了。没有装进去很好理解，就是V(i-1,j)；装进去了怎么理解呢？如果装进去第i件商品，那么装入之前是什么状态，肯定是V(i-1,j-w(i))。由于最优性原理（上文讲到），V(i-1,j-w(i))就是前面决策造成的一种状态，后面的决策就要构成最优策略。两种情况进行比较，得出最优。

  1. 填表，首先初始化边界条件，V(0,j)=V(i,0)=0；

  • 如，i=1，j=1，w(1)=2，v(1)=3，有j<w(1)，故V(1,1)=V(1-1,1)=0；
  • 又如i=1，j=2，w(1)=2，v(1)=3，有j=w(1),故V(1,2)=max｛ V(1-1,2)，V(1-1,2-w(1))+v(1) ｝=max｛0，0+3｝=3；
  • 如此下去，填到最后一个，i=4，j=8，w(4)=5，v(4)=6，有j>w(4)，故V(4,8)=max｛ V(4-1,8)，V(4-1,8-w(4))+v(4) ｝=max｛9，4+6｝=10……

最终表

  1. 表格填完，最优解即是V(number,capacity)=V(4,8)=10。

代码实现

尽管只有4个商品，但是我们创建的数组元素有5个,首元素补零。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<iostream>
using namespace std;
#include <algorithm>
 
int main()
{
	int w[5] = { 0 , 2 , 3 , 4 , 5 };			//商品的体积2、3、4、5
	int v[5] = { 0 , 3 , 4 , 5 , 6 };			//商品的价值3、4、5、6
	int bagV = 8;					        //背包大小
	int dp[5][9] = { { 0 } };			        //动态规划表
 
	for (int i = 1; i <= 4; i++) {//遍历背包物品
		for (int j = 1; j <= bagV; j++) {//遍历背包容量
			if (j < w[i])
				dp[i][j] = dp[i - 1][j];
			else
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
		}
	}
 
	//动态规划表的输出
	for (int i = 0; i < 5; i++) {
		for (int j = 0; j < 9; j++) {
			cout << dp[i][j] << ' ';
		}
		cout << endl;
	}
 
	return 0;
}

背包问题最优解回溯

通过上面的方法可以求出背包问题的最优解，但还不知道这个最优解由哪些商品组成，故要根据最优解回溯找出解的组成，根据填表的原理可以有如下的寻解方式：

  • V(i,j)=V(i-1,j)时，说明没有选择第i 个商品，则回到V(i-1,j)；
  • V(i,j)=V(i-1,j-w(i))+v(i)时，说明装了第i个商品，该商品是最优解组成的一部分，随后我们得回到装该商品之前，即回到V(i-1,j-w(i))；
  • 一直遍历到i＝0结束为止，所有解的组成都会找到。

就拿上面的例子来说吧：

  • 最优解为V(4,8)=10，而V(4,8)!=V(3,8)却有V(4,8)=V(3,8-w(4))+v(4)=V(3,3)+6=4+6=10，所以第4件商品被选中，并且回到V(3,8-w(4))=V(3,3)；

  • 有V(3,3)=V(2,3)=4，所以第3件商品没被选择，回到V(2,3)；

  • 而V(2,3)!=V(1,3)却有V(2,3)=V(1,3-w(2))+v(2)=V(1,0)+4=0+4=4，所以第2件商品被选中，并且回到V(1,3-w(2))=V(1,0)；

  • 有V(1,0)=V(0,0)=0，所以第1件商品没被选择。

代码实现

背包问题最终版详细代码实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<iostream>
using namespace std;
#include <algorithm>
 
int w[5] = { 0 , 2 , 3 , 4 , 5 };			//商品的体积2、3、4、5
int v[5] = { 0 , 3 , 4 , 5 , 6 };			//商品的价值3、4、5、6
int bagV = 8;					        //背包大小
int dp[5][9] = { { 0 } };			        //动态规划表
int item[5];					        //最优解情况
 
void findMax() {					//动态规划
	for (int i = 1; i <= 4; i++) {
		for (int j = 1; j <= bagV; j++) {
			if (j < w[i])
				dp[i][j] = dp[i - 1][j];
			else
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
		}
	}
}
 
void findWhat(int i, int j) {				//最优解情况
	if (i >= 0) {
		if (dp[i][j] == dp[i - 1][j]) {
			item[i] = 0;//当前序列物品没选中
			findWhat(i - 1, j);
		}
		else if (j - w[i] >= 0 && dp[i][j] == dp[i - 1][j - w[i]] + v[i]) {
			item[i] = 1;//当前序列物品被选中
			findWhat(i - 1, j - w[i]);
		}
	}
}
 
void print() {
	for (int i = 0; i < 5; i++) {			//动态规划表输出
		for (int j = 0; j < 9; j++) {
			cout << dp[i][j] << ' ';
		}
		cout << endl;
	}
	cout << endl;
 
	for (int i = 0; i < 5; i++)			//最优解输出
		cout << item[i] << ' ';
	cout << endl;
}
 
int main()
{
	findMax();
	findWhat(4, 8);
	print();
 
	return 0;
}

输出

1
2
3
4
5
6
7
0 0 0 0 0 0 0 0 0 
0 0 3 3 3 3 3 3 3 
0 0 3 4 4 7 7 7 7
0 0 3 4 5 7 8 9 9
0 0 3 4 5 7 8 9 10

0 0 1 0 1//第2 第4件商品被选中

例题

1.求一组最优解，但没标记背包内具体情况

使用二维数组m[i][j]存储背包剩余容量为j，可选物品为i、i+1、……、n时0-1背包问题的最优值。绘制

价值数组v = {8, 10, 6, 3, 7, 2}，

重量数组w = {4, 6, 2, 2, 5, 1}，

背包容量C = 12时对应的m[i] [j]数组。

0 1 2 3 4 5 6 7 8 9 10 11 12
1 0 0 0 8 8 8 8 8 8 8 8 8
2 0 0 0 8 8 10 10 10 10 18 18 18
3 0 6 6 8 8 14 14 16 16 18 18 24
4 0 6 6 9 9 14 14 17 17 19 19 24
5 0 6 6 9 9 14 14 17 17 19 21 24
6 2 6 8 9 11 14 16 17 19 19 21 24

(第一行和第一列为序号，其数值为0)

解释：

如m[2] [6],在面对第二件物品，背包容量为6时我们可以选择不拿，那么获得价值仅为第一件物品的价值8，如果拿，就要把第一件物品拿出来，放第二件物品，价值10，那我们当然是选择拿。m[2] [6]=m[1] [0]+10=0+10=10;依次类推，得到m[6] [12]就是考虑所有物品，背包容量为C时的最大价值。

则代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <iostream>
#include <cstring>
using namespace std;
 
 
const int N=15;
 
 
int main()
{
    int v[N]={0,8,10,6,3,7,2};//首项补个0
    int w[N]={0,4,6,2,2,5,1};
 
 
    int m[N][N];
    int n=6;//背包中物品数量
    int c=12;//背包最大重量
    memset(m,0,sizeof(m));//初始化二维数组m
    for(int i=1;i<=n;i++)//物品数量
    {
        for(int j=1;j<=c;j++)//放入新物体重量变化
        {
            if(j>=w[i])
                m[i][j]=max(m[i-1][j],m[i-1][j-w[i]]+v[i]);
 
 
            else
                m[i][j]=m[i-1][j];
        }
    }
 
 
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=c;j++)
        {
            cout<<m[i][j]<<' ';
        }
        cout<<endl;
    }
 
 
    return 0;
}

运行结果：

1
2
3
4
5
6
0 0 0 8 8 8 8 8 8 8 8 8 
0 0 0 8 8 10 10 10 10 18 18 18
0 6 6 8 8 14 14 16 16 18 18 24
0 6 6 9 9 14 14 17 17 19 19 24
0 6 6 9 9 14 14 17 17 19 21 24
2 6 8 9 11 14 16 17 19 19 21 24

到这一步，可以确定的是可能获得的最大价值，但是我们并不清楚具体选择哪几样物品能获得最大价值。

另起一个 x[ ] 数组，x[i]=0表示不拿，x[i]=1表示拿。

m[n] [c]为最优值，如果m[n] [c]=m[n-1] [c] ,说明有没有第n件物品都一样，则x[n]=0 ; 否则 x[n]=1。

当x[n]=0时，由x[n-1] [c]继续构造最优解；

当x[n]=1时，则由x[n-1] [c-w[i]]继续构造最优解。

以此类推，可构造出所有的最优解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void traceback()
{
    for(int i=n;i>1;i--)
    {
        if(m[i][c]==m[i-1][c])
            x[i]=0;
        else
        {
            x[i]=1;
            c-=w[i];
        }
    }
    x[1]=(m[1][c]>0)?1:0;
}

2.求最优解并标记

问题描述

某工厂预计明年有A、B、C、D四个新建项目，每个项目的投资额Wk及其投资后的收益Vk如下表所示，投资总额为30万元，如何选择项目才能使总收益最大？

Project Wk Vk
A 15 12
B 10 8
C 12 9
D 8 5 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <iostream>
#include <cstring>
using namespace std;
 
const int N=150;
 
int v[N]={0,12,8,9,5};
int w[N]={0,15,10,12,8};
int x[N];
int m[N][N];
int c=30;
int n=4;
void traceback()
{
    for(int i=n;i>1;i--)
    {
        if(m[i][c]==m[i-1][c])
            x[i]=0;
        else
        {
            x[i]=1;
            c-=w[i];
        }
    }
    x[1]=(m[1][c]>0)?1:0;
}
 
int main()
{
 
 
    memset(m,0,sizeof(m));
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=c;j++)
        {
            if(j>=w[i])
                m[i][j]=max(m[i-1][j],m[i-1][j-w[i]]+v[i]);
 
            else
                m[i][j]=m[i-1][j];
        }
    }/*
    for(int i=1;i<=6;i++)
    {
        for(int j=1;j<=c;j++)
        {
            cout<<m[i][j]<<' ';
        }
        cout<<endl;
    }
*/
    traceback();
    for(int i=1;i<=n;i++)
        cout<<x[i];
    return 0;
}

输出x[i]数组：0111，输出m[4] [30]：22。

得出结论：选择BCD三个项目总收益最大，为22万元。

不过这种算法只能得到一种最优解，并不能得出所有的最优解。

  • 版权声明： 本博客所有文章除特别声明外，著作权归作者所有。转载请注明出处！
  • Copyrights © 2020-2023 cyg
  • 访问人数: | 浏览次数: