本文主要内容来自网上流传的背包九讲，非常的经典，现以在github上开源，记录一下个人学习笔记和理解。

0 / 1背包

image-20201008230951893

实现代码：

1
2
3
4
5
6
7
8
int cost[N];//存每个物品的花费
int w[N];//存每个物品的价值
int dp[N][N];//dp[i][j]存储容量为j，且只考虑前i个物品时，能取得的最大价值
for(int i=1;i<=n;i++)
    for(int j=1;j<=v;j++)
        //j>cost[i]表示物品i可放入容量为j的背包中
        if(j>cost[i])dp[i][j]=max(dp[i-1][j],dp[i-1][j-cost[i]]+w[i]);
        else dp[i][j]=dp[i-1][j];//当物品i无法放入时，与只考虑前i-1个相同

image-20201008233725187

image-20201008233747347

代码：

1
2
3
4
5
6
7
8
9
10
11
12
//对于所有的容量考虑第i个取与不取的价值，记录再dp数组中，第二轮i+1个时，利用原dp数组更新自己(滚动数组)
	for(int i=1;i<=n;i++)
		//若j>=cost[i]改为j>=0，则循环体要加判断j能否放进cost[i]的情况
		//不能则dp[j]=dp[j],否则有dp[j]=dp[j-cost[i]]+weight[i]
		//而直接根据j>=cost[i]判断循环是否继续，放得进则j一定大于0
		for (int j = v; j >= cost[i]; j--)	
		{
			//在进行第i+1轮循环时，正要更新i+1状态下的dp[]，此时dp[]上每个空间j保存的是上一轮状态(i轮)时的dp[]
			//而更新dp[j]要用到上一个状态dp[j-cost[i]],若从0到v更新，更新j较大时，dp[j]时要用到的dp[j-cost[i]]已被修改，不符合，倒过来则不会
			//在执行下方语句时，max中dp[j]表示的是上一个状态下的dp[j]
			dp[j] = max(dp[j], dp[j - cost[i]] + weight[i]);
		}

image-20201008233815280

image-20201008234602622

这个常数优化代码待添加

01背包是所有背包问题的基础，其它背包问题都能转化为01背包，因此必须牢记算法思想原理。

完全背包

在原问题(本文中的原问题均指代基础的01背包问题)中，每个物品都只有一件，而当每个物品都有无数件可取时，这个问题就变成了完全背包。

解决方法就是在01背包的基础上，把内层循环的遍历顺序倒置。

1
2
3
for(int i=1;i<=n;i++)
	for (int j = cost[i]; j <= v; j++)
		dp[j] = max(dp[j], dp[j - cost[i]] + weight[i]);

考虑为什么倒置可以解决？

在01背包问题中，二维数组优化为一维数组时d[ j ]倒序填写，目的是不覆盖dp [ i-1 ] [ j]和dp[ i -1] [ j-cost[ i ] ]，因为dp[ i ] [ j ]的结果要依赖于dp[ i-1] [ … ]（即第i个物品还没有被考虑到取和不取），而若正序填dp[ j ]，当填到dp[ j ]时，dp[ k ] k<j的内容已经被覆盖了 ，也就是说在考虑第i件物品是否取的时候，dp[ k ]已经包含了该物品被取过的情况，而此时dp[ j ]依旧在考虑是否要取物品i，因此，此情况下物品可以无限取。

多重背包

在原问题中，当每个物品的数量可以为任意正整数时，求背包的最大价值，该问题就演变为了多重背包。

一个直观的想法就是，当该种物品有m件时，把它分割成m种物品，并且他们的数量均为1，话句话说，就是把每件物品都看成一个独一无二的种类，这样，当有a件A物品，b件B物品，c件C物品时进行分割，得到了a+b+c种物品，每种物品的数量为1，这就转化为了最基本的01背包问题。

代码：

1
2
3
4
5
6
7
8
cin >> v >> n;
for (int i = 1; i <= n; i++)
    cin >> cost[i] >> weight[i] >> kinds[i];
for (int i = 1; i <= n; i++)//第i重循环表示考虑物品i是否取
    //比01背包多了一个循环,表示物品i需要考虑kind[i]次，因为i有kind[i]件
    for (int k = 1; k <= kinds[i]; k++)	
        for (int j = v; j >= cost[i]; j--)
            dp[j] = max(dp[j], dp[j - cost[i]] + weight[i]);

例题：HDU2191

这种情况下，当一种物品的数量非常大时，实际上中间一层循环包含了很多无效的考虑。时间复杂度很高，在很多题目中，都可能出现超时，有两种优化的方式，分别是二进制思想优化和单调队列

二进制优化

二进制优化的原理
当一个物品有k件时，即，1，1，1…1 共k个1，需要考虑每件物品的取和不取的组合情况，也就是最终可能取得0到k
以19为例，如果我们拆分成1,2,4,8,3，每个数字有取和不取两种情况，那么可以组成0到19中的任意数，但是这样就可以把k个物品转化成大约logk个，极大降低了时间复杂度，但同时也增加了空间复杂度
那么五个数是怎么来的呢
其实就是相加小于等于该数的2的幂次方（1,2,4,8）和那个数与和的差值（3）

当一件物品的 件数X单件花费>总限制花费 时该物品相当于完全背包了，不需要优化，因每件物品最多取 总限制花费/单件花费 的数量

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
int dp[1000005];
int cost[1000005], weight[1000005];//拆分之后个数会变多，记得将数组开大
int main()
{
	int n, v, ans, cnt = 1; 
	scanf("%d%d", &n, &v);
	for (int i = 1; i <= n; i++)
	{
		int c, w, num;
		scanf("%d%d%d", &c, &w, &num);
		/*二进制拆分优化*/
		//这里可加一句判断是否数量超过相当于完全背包不需要优化的情况
		for (int j = 1; j <= num; j <<= 1)
		{
			cost[cnt] = j*w;
			weight[cnt] = j * c;
			cnt++;
			num -= j;
		}
		if (num) {
			cost[cnt] = num * w;
			weight[cnt] = num * c;
			cnt++;
		}
	}
	/*优化后正常的套用01背包*/
	for (int i = 1; i < cnt; i++)
		for (int j = v; j >= cost[i]; j--)
			dp[j] = max(dp[j], dp[j - cost[i]] + weight[i]);
	printf("%d\n", dp[v]);
	return 0;
}

例题：P1776 宝物筛选

单调队列优化，还没搞懂

混合背包

原问题中，当每种物品的数量既有1个也有多个，还可以有无限个的情况下，该问题就演变成了混合背包，实质上是前面三种背包情况的一个综合。

一个直观的想法就是分情况讨论，当在考虑某种物品取和不取时，

  • 若该种物品只有1件，则套用01背包的思路

  • 有无限件时则套用完全背包的思路，

  • 当为第三种情况则用多重背包实现

    实际上，第一种也可以归类到多重背包下，最终都会转化成01背包

搞懂了01背包、完全背包和多重背包后，剩下的就都是以上三种情况的运用和变形，我就直接简单的记录例题和题解。基本上每种做上两三个题目就明白了。

例题：p1833 樱花

题解：

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
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<malloc.h>
using namespace std;
int dp[1005];
int cost[1000000];	//二进制优化多重背包，故把数组开尽可能大
int value[1000000];
int kinds[1000000];
int main()
{
	int v, n;
	int h1, m1, h2, m2;
	char c;
	scanf("%d%c%d%d%c%d%d", &h1, &c, &m1, &h2, &c, &m2, &n);
	if (h2 > h1)v = (h2 - h1) * 60 + m2 - m1;
	else v = m2 - m1;
	int cnt = 1;
	for (int i = 1; i <= n; i++)
	{
		int c, v, k;
		scanf("%d%d%d", &c, &v, &k);
		if (k == 0) {	//完全背包
			cost[cnt] = c, value[cnt] = v, kinds[cnt] = 0;
			cnt++;
			continue;
		}
		for (int j = 1; j <= k; j <<= 1)	//多重背包的二进制优化
		{
			cost[cnt] = j * c, value[cnt] = j * v, kinds[cnt] = 1;
			k -= j;
			cnt++;
		}
		if (k) {
			cost[cnt] = k * c, value[cnt] = k * v, kinds[cnt] = 1;
			cnt++;
		}
	}
	for (int i = 1; i < cnt; i++)
	{
		if (kinds[i] == 0) {	//完全背包
			for (int j = cost[i]; j <= v; j++)
				dp[j] = max(dp[j], dp[j - cost[i]] + value[i]);
		}
		else {	//多重背包（二进制优化后即为01背包）
				for (int j = v; j >= cost[i]; j--)
					dp[j] = max(dp[j], dp[j - cost[i]] + value[i]);
		}
	}
	printf("%d\n", dp[v]);
	return 0;
}

二维费用背包

在原问题中，当限制物品取和不取的条件除了背包容量外，还增加了一个新的约束条件时，原问题就演变为二维费用背包问题，即对于每件物品，具有两种不同的费用；选择这件物品必须同时付出这两种代价；对于每种代价都有一个可付出的最大值（背包容量）

解决方法：

image-20201009125956288

例题： p1855 榨取kkksc03 HDU2159 FATE

题解：

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
//p1855 榨取kkksc03
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<malloc.h>
using namespace std;
int dp[201][201];
int money[101];
int times[101];
int main()
{
	int n, m, t;
	cin >> n >> m >> t;
	for (int i = 1; i <= n; i++)
	{
		cin >> money[i] >> times[i];
	}
	for (int i = 1; i <= n; i++)	//对每个愿望进行处理
	{
		for (int j = m; j >= money[i]; j--)//第一维费用
		{
			for (int k = t; k >= times[i]; k--)//第二维费用
				dp[j][k] = max(dp[j][k], dp[j - money[i]][k- times[i]]+1);
		}
	}
	printf("%d\n", dp[m][t]);
	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
//HDU2159 FATE 
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
int dp[101][101];	//dp[i][j]表示忍耐度不超过j，击杀不超过杀i只怪时获得的经验
int expe[101];
int tor[101];
int main()
{
	int e, t, k, m;	//分别表示expe,tor,kind,max

	while (scanf("%d%d%d%d", &e, &t, &k, &m) != EOF)
	{
		memset(dp, 0, sizeof(dp));
		for (int i = 1; i <= k; i++)
		{
			scanf("%d%d", &expe[i], &tor[i]);
		}
		for (int i = 1; i <= k; i++)
			for (int j = tor[i]; j <= t; j++)
				for (int k = 1;k <= m; k++)
					dp[j][k] = max(dp[j][k], dp[j - tor[i]][k - 1]+expe[i]);
		if (dp[t][m] < e) printf("-1\n");
		else
		{
			int i;//寻找满足升级条件的最小耗费忍耐度
			for (i = 1; i <= t; i++)//不是找最小击杀数，不用二重循环从1-m枚举
				if (dp[i][m] >= e)break;	//找到最小值
			printf("%d\n", t - i);
		}
	}
	return 0;
}

分组背包问题

在原问题中，当所有的物品被划分为若干组，每组中的物品互相冲突，最多选一件时，原问题就演变为分组的背包问题。

image-20201009130821766

例题 P1757 通天之分组背包

题解：

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
//P1757 通天之分组背包
#include<cstdio>
#include<vector>
#include<algorithm>
#define N 1001
using namespace std;
struct Node {
	int c;
	int v;
};
int dp[N];
vector<Node> cost[N];
int main()
{
	int v,n;
	int numOfGroup = -1;
	scanf("%d%d", &v, &n);
	for (int i = 1; i <= n; i++)
	{
		int c, v, g;
		scanf("%d%d%d", &c, &v, &g);
		if (g > numOfGroup)numOfGroup = g;
		Node t;
		t.c = c, t.v = v;
		cost[g].push_back(t);
	}
		
	for(int i=1;i<=numOfGroup;i++)	//这层循环是对每组的遍历，考虑每组的选和不选
		for(int j=v;j>=0;j--)		//这层是枚举容量，v枚举至0
			for (vector<Node>::iterator it = cost[i].begin(); it != cost[i].end(); it++)//这层循环是遍历每组中的物品,考虑取该组中的哪一个物品可以使得价值dp[j]最大
			{
				if(j>=it->c)	//判断能否放得进
					dp[j] = max(dp[j], dp[j - it->c] + it->v);	//01背包的状态转移方程，判断每组中放入的哪一个物品(不选)使得dp[j]最大
			}
	printf("%d",dp[v]);
}

有依赖关系的背包

例题： 金明的预算方案

题解：

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
//P1064 金明的预算方案 （01背包+分组背包解法）
#include<bits/stdc++.h>
using namespace std;
struct Node {
	int c, v, k;	//花费，价值，所属
}node[60];
int dp[32005];
int group[32005];
int main()
{
	int n, v;	
	cin >> v >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> node[i].c >> node[i].v >> node[i].k;
		node[i].v *= node[i].c;
	}
	for (int i = 1; i <= n; i++)//枚举每一个物品 
	{
		if (node[i].k == 0)	//第i件为主件
		{
			//那么接下来的操作都是针对当前主件所属的组的选择
			//也就是说后面的操作都是基于当前主件选择了的情况下的 
			memset(group, 0, sizeof(group));
			//先把主件考虑进来，各组的操作都要把主件考虑在内
			for (int j = v; j >= node[i].c; j--)//本应该是逆序（但是属于组里01背包第一个考虑的物品可正可逆）
				group[j] = dp[j - node[i].c] + node[i].v;
			//接下来考虑该主件的所有附件
			for (int k = 1; k <= n; k++)
				if (node[k].k == i) {	//属于本组的附件
					for (int j = v; j >= node[k].c + node[i].c; j--)//进行01背包，此时背包容量的下界是本附件花费加上主件的花费
						group[j] = max(group[j], group[j - node[k].c] + node[k].v);
				}
			//该组01背包后的最优解group[]与dp[]更新求最大值	
			for (int k = node[i].c; k <= v; k++)
				dp[k] = max(group[k], dp[k]);
		}
		
	}
	cout << dp[v] << endl;
	return 0;
}

泛化物品

背包问题问法的变化

最后两章以及前几章中的其它优化方案，自行阅读背包九讲原文

本文大部分内容来源于背包九讲，并根据一年前做过的题解，结合个人对的学习理解和网上的思路整体而成，可能有少许内容，当时参考了很多博客，链接也没保存，侵删。