动态规划之背包问题

动态规划之背包问题

作为算法界的经典，背包问题一直是动态规划的一个代表，也是给了无数算法新人一记迎头痛击啊，我也是被其困扰了好长一段时间，连最基础的模板都很难理解，更别说无尽的变体了，今天我就来带大家回顾一下基础模板的思路。

01背包

题面：

N 件物品和一个容量是 V 的背包。每件物品只能使用一次。

第 i件物品的体积是 v[i]，价值是 w[i]。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。

输出最大价值。

代码：

int main()
{
    int n, m, v[1010] = { 0 }, w[1010] = { 0 }, dp[1010]= { 0 };
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d %d", &v[i], &w[i]);
    for (int i = 1; i <= n; i++)
        for (int j = m; j >= v[i]; j--)
            dp[j] = max (dp[j], dp[j - v[i]] + w[i]);
    printf("%d", dp[m]);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11

题解：

状态转移方程：dp[j] = max (dp[j], dp[j - v[i]] + w[i]);

考虑前i个物品在空间为j的情况下的最优解，要加入当前物品需要预留空间，则将当前与腾出空间后加上当前物品价值对比得出当前最优解。

值得注意的是第二层j循环从大到小遍历直到不可能装下当前物品，若从小到大则可能会发生前面的情况影响后面的情况，导致一件物品被装入多次，而从大到小则不会。

---

二维01背包

题面：

洛谷 P1507 NASA的食物计划

航天飞机的体积有限，当然如果载过重的物品，燃料会浪费很多钱，每件食品都有各自的体积、质量以及所含卡路里。在体积和质量的最大值的情况下，请输出能达到的食品方案所含卡路里的最大值，当然每个食品只能使用一次。

代码：

int main()
{
	int H, T, n;
	scanf("%d %d", &H, &T);
	scanf("%d", &n);
	int h[60], t[60], k[60], dp[500][500] = { 0 };
	for (int i = 1; i <= n; i++) 	
	{
		scanf("%d %d %d", &h[i], &t[i], &k[i]);
		for (int j = H; j >= h[i]; j--)
			for (int m = T; m >= t[i]; m--)
				dp[j][m] = max(dp[j][m], dp[j - h[i]][m - t[i]] + k[i]);
	}
	printf("%d", dp[H][T]);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

题解：

状态转移方程：dp[j][m] = max(dp[j][m], dp[j - h[i]][m - t[i]] + k[i]);

在01背包的基础上，dp数组多开一维度，多进行一层循环，在这题中，dp[j][m]中j表示体积，m表示质量。

同样是从大到小遍历防止同一个食物放入两次。

---

完全背包

题面

N 件物品和一个容量是 V 的背包。每件物品可无限使用。

第 i件物品的体积是 v[i]，价值是 w[i]。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。

输出最大价值。

代码：

int main()
{
    int n, m, v[1010] = { 0 }, w[1010] = { 0 }, dp[1010]= { 0 };
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d %d", &v[i], &w[i]);
    for (int i = 1; i <= n; i++)
        for (int j = 0; j <m; j++)
            dp[j] = max (dp[j], dp[j - v[i]] + w[i]);
    printf("%d", dp[m]);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11

题解：

状态转移方程：dp[j] = max (dp[j], dp[j - v[i]] + w[i]);

和01背包不同，第二层j循环从小到大，用多装的情况覆盖少的情况，正好可以考虑无限次数的使用。

---

多重背包

题面

有N种物品和一个容量是V的背包。

第i种物品最多有s[i]件，每件体积是v[i]，价值是w[i]。

求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。

输出最大价值。

代码：

int main()
{
	int n, m, dp[1010] = { 0 }, s[1010] = { 0 }, w[1010] = { 0 }, v[1010] = { 0 };
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; i++) scanf("%d %d %d", &v[i], &w[i], &s[i]);
	for (int i = 1; i <= n; i++)
		for (int j = m; j >= 1; j--)
			for (int k = 0; k * v[i] <= j && k <= s[i]; k++)
				dp[j] = max(dp[j], dp[j - k * v[i]] + k * w[i]);
	printf("%d", dp[m]);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12

题解：

状态转移方程：dp[j] = max(dp[j], dp[j - k * v[i]] + k * w[i]);

多重背包类似01背包，将多个相同的物体拆开来考虑，我们只需要在01背包的基础上，加入第三层循环，来考虑每个物体放入的个数，即可完成此题，但当数据量过大时，O（n³）的复杂度显然是难以接受的，所以在多重背包我们往往会用到二进制优化。

---

多重背包——二进制优化

题面

有N种物品和一个容量是V的背包。

第i种物品最多有s[i]件，每件体积是v[i]，价值是w[i]。

求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。

输出最大价值。

代码：

int main()
{
	int n, m, dp[2010] = { 0 }, w[2010] = { 0 }, v[2010] = { 0 };
	int a, b, c, count = 1;
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; i++) 
	{
		scanf("%d %d %d", &a, &b, &c);
		for (int j = 1; c > j; j *= 2)
		{
			v[count] = j * a;
			w[count] = j * b;
			count++;
			c -= j;
		}
		v[count] = c * a;
		w[count] = c * b;
		count++;
	}
	count--;
	for (int i = 1; i <= count; i++)
		for (int j = m; j >= v[i]; j--)
			dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
	printf("%d", dp[m]);
	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

题解：

状态转移方程：dp[j] = max(dp[j], dp[j - v[i]] + w[i]);

根据二进制的性质，我们完全可以用二进制的形式来表达一个数，或者更简单，我们只需要用二进制表达其中的一部分，使得比这个数小的任何数都能被这几个部分组成即可，这样，我们就通过数个组分的组合，完成了所有可能的数量。

如上，我们用若干偶数和一个余数，将所有的物体给拆分为若干组分，每个组分的体积和质量的都是单个物体的若干份，这样，我们就将多重背包转换为了01背包。

---

分组背包

题面

有N种物品和一个容量是V的背包。

每组物品有若干个，同一组内的物品最多只能选一个。

每件物品的体积是v [i][j]，价值是w[i][j]，其中i是组号j是组内编号。。

求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。

输出最大价值。

代码：

int main()
{
	int n, m,s, v[1010] = { 0 }, w[1010] = { 0 }, dp[1010] = { 0 };
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &s);
		for (int j = 1; j <= s; j++) scanf("%d %d", &v[j], &w[j]);
		for (int j = m; j > 0; j--)
			for (int k = 1; k <= s; k++)
				if (j >= v[k])
					dp[j] = max(dp[j], dp[j - v[k]] + w[k]);
	}
		printf("%d", dp[m]);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

题解：

状态转移方程：dp[j] = max(dp[j], dp[j - v[k]] + w[k]);

分组背包与01背包类似，我们分组考虑，在某一组考虑完之后我们再进入下一组，第二层循环从大到小遍历直到不可能装下当前组物品，因为从小到大装会导致同一组装入多个物品，已经装入的东西会影响后面的情况。

---

总结

以上便是背包问题模板的总结，本文由凉茶coltea撰写，转载请注明出处。请注明出处。