算法学习17-动态规划01：背包问题_动态规划 背包问题

算法学习17：背包问题（动态规划）

---

---

前言

---

提示：以下是本篇文章正文内容：

一、01背包问题：

---

1.朴素版：（二维）

---

---

---

---

// 例题：有n件物品，和一个容量是m的背包，每件物品只能使用一次。
// 第i件物品的体积是vi，价值是wi，
// 求将哪些物品装入背包，可以使总价值最大。
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

int n, m;
int v[N], w[N];// v：体积， w：价值
int f[N][N];// 从前i件物品中取，放到容量为j的背包中，最大的价值。 

int main()
{
	cin >> n >> m;
	for(int i = 1; i <= n; i ++) cin >> v[i] >> w[i];
	
	for(int i = 1; i <= n; i ++)
		for(int j = 0; j <= m; j ++)
		{
			f[i][j] = f[i - 1][j];// 不取 
			if(j >= v[i]) f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);// 取 
		}
		
	cout << f[n][m] << endl;
	return 0;
 } 
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

---

---

---

---

2.优化版：（一维）

// 优化版：
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

int n, m;
int v[N], w[N];// v：体积， w：价值 
int f[N];// 从i件物品中去，放到容量为j的背包，最大的价值。
// 注意要执行i轮循环 

int main()
{
	cin >> n >> m;
	for(int i = 1; i <= n; i ++) cin >> v[i] >> w[i];
	
	for(int i = 1; i <= n; i ++)
		// 注意1：如果这里不是倒着遍历，那么可能存在，在前面的时候，i物品已经被放进背包了 
		// 从大到小，保证前面的“状态”，还没有更新过。 
		for(int j = m; j >= v[i]; j --)
			// 不取 和 取 
			f[j] = max(f[j], f[j - v[i]] + w[i]);
		
	cout << f[m] << endl;
	return 0;
 } 
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

---

---

二、完全背包

1.朴素版：（3重for）

---

---

---

---

// 例题：有n种物品，容量为m的背包，“每种物品都有无限件可用”。
// 第i件物品的体积是vi，价值是wi，
// 求将哪些物品装入背包，可以使总价值最大，输出最大价值。
#include <iostream>
#include <algorithm>

using namespace std; 

const int N = 1010;

int n, m;
int v[N], w[N];
int f[N][N];

int main()
{
	cin >> n >> m;
	for(int i = 1; i <= n; i ++) cin >> v[i] >> w[i];
	
	// 3重for循环： 
	for(int i = 1; i <= n; i ++) 
		for(int j = 0; j <= m; j ++)
			for(int k = 0; k * v[i] <= j; k ++)
			 f[i][j] = max(f[i][j], f[i - 1][j - v[i] * k] + w[i] * k);
			 
	cout << f[n][m] << endl;
	return 0;
}
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

---

---

---

---

---

---

2.稍微优化版：（二维）

---

---

#include <iostream>
#include <algorithm>

using namespace std; 

const int N = 1010;

int n, m;
int v[N], w[N];
int f[N][N];

int main()
{
	cin >> n >> m;
	for(int i = 1; i <= n; i ++) cin >> v[i] >> w[i];

	for(int i = 1; i <= n; i ++) 
		for(int j = 0; j <= m; j ++)
			{
			// 这样就和01背包问题有点像了 
			// 不同的是：f[i - 1][j - v[i]] + w[i] 
			f[i][j] = f[i - 1][j]; 
			// 注意1：要加一个判断条件 （否者越界） 
		 	if(j >= v[i]) f[i][j] = max(f[i][j], f[i][j - v[i]] + w[i]);
			}
		
			 
	cout << f[n][m] << endl;
	return 0;
}
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

---

---

3.完全背包问题模版：（最终优化版）

#include <iostream>
#include <algorithm>

using namespace std; 

const int N = 1010;

int n, m;
int v[N], w[N];
int f[N];

int main()
{
	cin >> n >> m;
	for(int i = 1; i <= n; i ++) cin >> v[i] >> w[i];

	for(int i = 1; i <= n; i ++) 
		// 为什么是从前往后遍历，因为每件物品可以使用无限次，不存在重复问题 
		for(int j = v[i]; j <= m; j ++)
		 	f[j] = max(f[j], f[j - v[i]] + w[i]);
		
	cout << f[m]<< endl;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

三、多重背包

1.朴素版：（）

---

---

---

---

---

---

2.多重背包问题的“二进制优化”：

---

---

/*
多重背包问题的“二进制优化”： 
请先记住：二进制数的组合可以表示一个0~s范围内的十进制数
那么我们将总数量为s的一个“大包裹”转换为“1 2 4 8 16 32 64 .......”这样的小包裹

然后对于：这些小包裹，我们选择“取或者不取”，这样就把“多重背包问题”转换为“01背包问题” 
*/
/*
注意：为什么要优化？
第一种也可以使用，但是当数据范围大的时候就是出现Time Limit Exceed问题。
（1）0< n, m <100   0< vi, wi, si <100
（2）0 < n <1000 0 < m < 2000 0 < vi, wi, si <2000
const int N = 25000 是如何得到的？1000 * log2(2000) = 1000 * 11 = 22000
*/
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 25000, M = 2010;

int n, m;
int v[N], w[N];
int f[N];

int main()
{
	cin >> n >> m;
	int cnt = 0;// 标记 ：作为打包后的总数量 
	for(int i = 1; i <= n; i ++)
	{
		int a, b, s;// 体积，容量，数量 
		cin >> a >> b >> s;
		int k = 1;
		while(k <= s)
		{
			cnt ++;
			v[cnt] = a * k;// 打包后的体积 
			w[cnt] = b * k;// 打包后的容量 
			s -= k;// 剩余的总数量 
			k *= 2;// 打包的件数 
		}
		if(s > 0)// 多了 
		{
			cnt ++;
			v[cnt] = a * s;
			w[cnt] = b * s;
		}
	}
	
	n = cnt;// 打包后的所有包裹的数量
	// 此时，又相当于01背包问题 
	for(int i = 1; i <= n; i ++)
		for(int j = m; j >= v[i]; j --)
			f[j] = max(f[j], f[j - v[i]] + w[i]); 
	
	cout << f[m] << endl;	
	return 0;
 } 
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
58
59

---

---

四、分组背包

---

---

// 有n组物品，容量为m的背包，
// 每组物品有若干个，同一组内的物品最多只能选一个
// 每件物品的体积是vij，价值是wij，其中i是组号，j是组内编号
// 求将哪些物品装入背包，可以使总价值最大，输出最大价值。

/*
输入：n，m
接下来n组数据：
第一行：s表示这一组物品的数量
接下来s行：v，w 
*/

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110;

int n, m;
int v[N][N], w[N][N], s[N];
int f[N]; 

int main()
{
	cin >> n >> m;
	for(int i = 1; i <= n; i ++)
	{
		cin >> s[i];
		for(int j = 0; j <s[i]; j ++)
			cin >> v[i][j] >> w[i][j];
	}
	
	for(int i = 1; i <= n; i ++)
		// 像01背包：“取或不取”，只有一件，不可以重复，那么就倒着遍历，保证前面是未更新的 
		for(int j = m; j >= 0; j --)
			for(int k = 0; k < s[i]; k ++)
				if(v[i][k] <= j)
					f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
					
	cout << f[m] << endl;
	return 0;
 } 
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

---

---

总结

提示：这里对文章进行总结：