Acwing-基础算法课笔记之动态规划（背包问题）-Toy模板网

这篇具有很好参考价值的文章主要介绍了Acwing-基础算法课笔记之动态规划（背包问题）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一、01背包问题

1、概述

01背包中的0和1指的是放与不放，而且不能出现放多个的情况，背包只能放相同物品中的一个；
首先是对 $d [i] [j]$ 数组的解释，该数组表示的是只看前 $i$ 个物品，总体积是 $j$ 的情况下，总价值最大是多少；

2、过程模拟

不选第 $i$ 个物品，只考虑前 $i - 1$ 个物品， $d p [i] [j] = d p [i - 1] [j]$
选第 $i$ 个物品， $d p [i] [j] = d p [i - 1] [j - v [i]]$
$dp[i][j]=max\{1,2\}$
初始条件，一个物品都不考虑 $d p [0] [0] = 0$

背包的最大容量为 $6$ 。

物品	体积 $v$	价值 $w$
$A$	$2$	$3$
$B$	$3$	$5$
$C$	$4$	$6$

	$1$	$2$	$3$	$4$	$5$	$6$
$0$	0	0	0	0	0	0
$1$ $A (2, 3)$
$2$ $B (3, 5)$
$3$ $C (4, 6)$

$\Downarrow$
$\bullet$ 对于每一个单元格 $i . w e i g h t > j$ 是否成立，按行填写

	$1$	$2$	$3$	$4$	$5$	$6$
$0$	0	0	0	0	0	0
$1$ $A (2, 3)$	0	3	3	3	3	3
$2$ $B (3, 5)$
$3$ $C (4, 6)$

$\Downarrow$

	$1$	$2$	$3$	$4$	$5$	$6$
$0$	0	0	0	0	0	0
$1$ $A (2, 3)$	0	3	3	3	3	3
$2$ $B (3, 5)$	0	3	5	5	8	8
$3$ $C (4, 6)$

$\Downarrow$

	$2$	$3$	$4$	$5$	$6$
$0$	0	0	0	0	0
$1$ $A (2, 3)$	3	3	3	3	3
$2$ $B (3, 5)$	3	5	5	8	8
$3$ $C (4, 6)$	3	5	6	8	9

滚动dp一维数组版

	$0$	$1$	$2$	$3$	$4$	$5$	$6$
$0$	0	0	0	0	0	0	0

$\Downarrow$

	$0$	$1$	$2$	$3$	$4$	$5$	$6$
$1$ $A (2, 3)$	0	0	3	3	3	3	3

$\Downarrow$

	$0$	$1$	$2$	$3$	$4$	$5$	$6$
$2$ $B (3, 5)$	0	0	3	5	5	8	8

$\Downarrow$

	$0$	$1$	$2$	$3$	$4$	$5$	$6$
$3$ $C (4, 6)$	0	0	3	5	6	8	9

二、完全背包问题

1、概述

有 $n$ 件物品，每件物品的重量为 $w [i]$ ，价值为 $c [i]$ 。现有一个容量为 $V$ ，的背包，问如何选取物品放入背包，使得背包物品的总价值最大。其中每件物品有无穷件。
既然这样，不妨像0-1背包问题那样，先写出状态转移方程，从源头上摸索。

2、闫氏dp分析完全背包问题

$dp\begin{cases} 状态表示(i,j)\begin{cases} 集合：所有只从前i个物品中选，总体积不超过j的方案的集合 \\ 属性：max \end{cases} \\ 状态计算dp[i][j]=max(dp[i-1][j],f[i-1][j-v]+w、f[i-1][j-2v]+2w、......)，dp[i][j-v]=max(dp[i-1][j-v],f[i-1][j-2v]+w、f[i-1][j-3v]+2w、......)+w，两式组合dp[i][j]=max(dp[i-1][j],f[i][j-v]+w)如下图选第i个物品 \end{cases}$

Acwing-基础算法课笔记之动态规划（背包问题）,Acwing基础算法课笔记,算法,笔记,动态规划

3、过程模拟

例如：

						容量j
组号	物品	体积v	价值w	1	2	3	4	5	6	7
0	（无）	0	0	0	0	0	0	0	0	0
1	小古银手办	2	1	0	1	1	2	2	3	3
2	平板电脑	3	3	0	1	3	3	4	6	6
3	笔记本电脑	4	5	0	1	3	5	5	6	8
4	无价之宝	5	0	0	1	3	5	5	6	8

规律：
$\bullet$ 当 $j<v_i$ 的时候， $w_{i,j}=w_{i-1,j}$ （解释：如果当前物品装不进背包，最大价值和前 $i - 1$ 个物品的最大价值一样）
$\bullet$ 当 $j\ge v_i$ 的时候， $w_{i,j}=max(w_{i-1,j}$ 不装，装 $)$ （解释：如果装的下，在装和不装中选最大价值）

代码模板

int m = 0;
int n = 0;
cin >> m >> n;
int v[40] = {};
int w[40] = {};
for (int i = 1; i <= n; i ++){
    cin >> v[i] >> w[i];
}
int dp[40][210] = {};
for (int i = 1; i <= n; ++ i) {
    for (int j = 1; j <= m; ++ j) {
        if (j < v[i]) {
           dp[i][j] = dp[i - 1][j];
        }
        else {
           dp[i][j] = max(dp[i - 1][j], dp[i][j - v[i]] + w[i])
        }
    }
}
cout << "max = " << dp[n][m] <<endl;

优化版代码：

int m = 0;
int n = 0;
cin >> m >> n;
int v[40] = {};
int w[40] = {};
for (int i = 1; i <= n; i ++){
    cin >> v[i] >> w[i];
}
int dp[40][210] = {};
for (int i = 1; i <= n; ++ i) {
    for (int j = v[i]; j <= m; ++ j) {
        dp[j] = max(dp[j], dp[j - v[i]] + w[i])
    }
}
cout << "max = " << dp[n][m] <<endl;

三、多重背包问题

1、概述

求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大，但要注意的是，每件要取物品不能超过他给出的最大数量。

2、过程模拟

for(int i = 0; i < n; i ++)
   for(int j = m; j >= v[i]; j --)
      dp[j] = max(dp[j], dp[j - v[i]] + w[i], dp[j - 2 * v[i]] + 2 * w[i],......)//每件物品可以不去，可以取1个，或者取2个等等。

3、多重背包问题的优化版本

假设有一种物品有 $s$ 件，若要将其拆分开来，则从 $1$ 开始循环，每进行一次循环就乘 $2$ ，并每循环一次就减去迭代的变量 $i$ ，代码如下：

while (n--) {
	int v, w, s;
	scanf("%d%d%d", &v, &w, &s);
	for (int i = 1; i <= s; i *= 2) {
		s -= i;
		goods.push_back({ v * i,w * i });
	}
	if (s > 0)goods.push_back({ v * s,w * s });
}

分组背包问题

1、概述

有 $N$ 组物品和一个容量是 $V$ 的背包。每组物品有若干个，同一组内的物品最多只能选一个。每件物品的体积是 $v_{ij}$ ，价值是 $w_{ij}$ ，其中 $i$ 是组号， $j$ 是组内编号。

2、过程模拟

例如：
$\bullet$ 一个组只能选一个物品

组号	物品	体积v	价值w
1	小古银手办	2	1
	平板电脑	3	3
2	笔记本电脑	4	5
3	无价之宝	5	0

以下是动态模拟：
$\bullet$ 每个组都有装和不装两种情况
$\bullet$ 如果装某个组的话，这个组只能装一次文章来源地址https://www.toymoban.com/news/detail-854940.html

				容量j
组号	1	2	3	4	5	6	7
0	0	0	0	0	0	0	0
1
2
3

3、代码演示

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 110;
int n, m;
int v[N], w[N], dp[N];
int main() {
	scanf("%d%d", &n, &m);
	while (n--) {
		int s;
		scanf("%d", &s);
		for (int i = 0; i < s; i++)
			scanf("%d%d", &v[i], &w[i]);
		for (int j = m; j >= 0; j--) {
			for (int k = 0; k < s; k++) {
				if (j >= v[k]) {
					dp[j] = max(dp[j], dp[j - v[k]] + w[k]);
				}
			}
		}
	}
	printf("%d", dp[m]);
	return 0;
}