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

一、01背包问题

1、概述

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

2、过程模拟

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

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

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

$$\Downarrow$$

$$\Downarrow$$

滚动dp一维数组版

$$\Downarrow$$

$$\Downarrow$$

$$\Downarrow$$

二、完全背包问题

1、概述

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

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

d p { 状态表示 ( i , j ) { 集合：所有只从前 i 个物品中选，总体积不超过 j 的方案的集合 属性： m a x 状态计算 d p [ i ] [ j ] = m a x ( d p [ i − 1 ] [ j ] , f [ i − 1 ] [ j − v ] + w 、 f [ i − 1 ] [ j − 2 v ] + 2 w 、 . . . . . . ) ， d p [ i ] [ j − v ] = m a x ( d p [ i − 1 ] [ j − v ] , f [ i − 1 ] [ j − 2 v ] + w 、 f [ i − 1 ] [ j − 3 v ] + 2 w 、 . . . . . . ) + w ，两式组合 d p [ i ] [ j ] = m a x ( d p [ i − 1 ] [ j ] , f [ i ] [ j − v ] + w ) 如下图选第 i 个物品 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} dp⎩ ⎨ ⎧​状态表示(i,j){集合：所有只从前i个物品中选，总体积不超过j的方案的集合属性：max​状态计算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个物品​

3、过程模拟

例如：

规律：
$\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;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

优化版代码：

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
3
4
5
6
7
8
9
10
11
12
13
14
15

三、多重背包问题

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个等等。
1
2
3

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
2
3
4
5
6
7
8
9

分组背包问题

1、概述

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

2、过程模拟

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

以下是动态模拟：
$\bullet$每个组都有装和不装两种情况
$\bullet$如果装某个组的话，这个组只能装一次

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24