❤ 作者主页：欢迎来到我的技术博客😎
❀ 个人介绍：大家好，本人热衷于Java后端开发，欢迎来交流学习哦！(￣▽￣)~*
🍊 如果文章对您有帮助，记得关注、点赞、收藏、评论⭐️⭐️⭐️
📣 您的支持将是我创作的动力，让我们一起加油进步吧！！！🎉🎉
第一章 背包问题
一、01背包问题
1. 题目描述
有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。
第 i 件物品的体积是 v i v_i vi，价值是 w i w_i wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。
输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。
接下来有 N 行，每行两个整数 v i , w i v_i,w_i vi,wi，用空格隔开，分别表示第 ii 件物品的体积和价值。
输出格式
输出一个整数，表示最大价值。
数据范围
0
<
N
,
V
≤
1000
0<N,V≤1000
0<N,V≤1000
0
<
v
i
,
w
i
≤
1000
0<v_i,w_i≤1000
0<vi,wi≤1000
输入样例
4 5
1 2
2 4
3 4
4 5
输出样例：
8
2. 思路分析
版本一： 二维数组
（1）状态 f[i][j] 定义：前
i
i
i 个物品，背包容量是
j
j
j 下的最优解（最大价值）：
- 当前的状态依赖于之前的状态，可以理解为从初始状态
f[0][0] = 0开始决策，有 N 件物品，则需要 N 次决 策，每一次对第 i i i 件物品的决策，状态f[i][j]不断由之前的状态更新而来。
(2) 当前背包容量不够（j < v[i]），没得选，因此前
i
i
i 个物品最优解即为前
i
−
1
i−1
i−1 个物品最优解：
- 状态转移方程：
f[i][j] = f[i - 1][j]
(3) 当前背包容量够，可以选，因此需要决策选与不选第 i i i 个物品：
- 选：
f[i][j] = f[i - 1][j - v[i]] + w[i] - 不选：
f[i][j] = f[i - 1][j] - 我们的决策是如何取到最大价值，因此以上两种情况取 最大值。
代码如下：
#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int v[N]; // 体积
int w[N]; // 价值
int f[N][N]; // f[i][j], j体积下前i个物品的最大价值
int main()
{
int n, m;
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 = 1; j <= m; j++)
{
// 当前背包容量装不进第i个物品，则价值等于前i-1个物品
if(j < v[i])
f[i][j] = f[i - 1][j];
// 能装，需进行决策是否选择第i个物品
else
f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);
}
cout << f[n][m] << endl;
return 0;
}
版本二： 一维数组
将状态 f[i][j] 优化到一维 f[j]，实际上只需要做一个等价变形。
为什么可以这样变形呢？我们定义的状态 f[i][j] 可以求得任意合法的
i
i
i 与
j
j
j 最优解，但题目只需要求得最终状态 f[n][m] ，因此我们只需要一维的空间来更新状态。
(1) 状态 f[j] 定义：N 件物品，背包容量
j
j
j 下的最优解。
(2) 注意枚举背包容量 j j j 必须从 m m m 开始。
(3) 为什么一维情况下枚举背包容量需要逆序？ 在二维情况下，状态 f[i][j] 是由上一轮i - 1的状态得来的，f[i][j] 与 f[i - 1][j] 是独立的。而优化到一维后，如果我们还是正序，则有f[较小体积] 更新到f[较大体积]，则有可能本应该用第i-1 轮的状态却用的是第 i 轮的状态。
(4) 例如，一维状态第 i 轮对体积为 3 的物品进行决策，则 f[7] 由 f[4] 更新而来，这里的 f[4] 正确应该是 f[i - 1][4]，但从小到大枚举j这里的 f[4] 在第i轮计算却变成了 f[i][4]。当逆序枚举背包容量j时，我们求 f[7] 同样由 f[4] 更新，但由于是逆序，这里的 f[4] 还没有在第 i 轮计算，所以此时实际计算的 f[4] 仍然是 f[i - 1][4]。
(5) 简单来说，一维情况正序更新状态 f[j] 需要用到前面计算的状态已经被「污染」，逆序则不会有这样的问题。
(6) 状态转移方程： f[j] = max(f[j], f[j - v[i]] + w[i]
for(int i = 1; i <= n; i++)
for(int j = m; j >= 0; j--)
{
if(j < v[i])
f[i][j] = f[i - 1][j]; // 优化前
f[j] = f[j]; // 优化后，该行自动成立，可省略。
else
f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]); // 优化前
f[j] = max(f[j], f[j - v[i]] + w[i]); // 优化后
}
实际上，只有当枚举的背包容量 j>= v[i] 时才会更新状态，因此我们可以修改循环终止条件进一步优化。
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]);
关于状态 f[j] 的补充说明:
二维下的状态定义 f[i][j] 是前
i
i
i 件物品，背包容量
j
j
j 下的最大价值。一维下，少了前
i
i
i 件物品这个维度，我们的代码中决策到第
i
i
i 件物品（循环到第i轮），f[j] 就是前i轮已经决策的物品且背包容量
j
j
j 下的最大价值。
因此当执行完循环结构后，由于已经决策了所有物品，f[j] 就是所有物品背包容量
j
j
j 下的最大价值。即一维 f[j] 等价于二维 f[n][j]。
版本三： 优化输入
我们注意到在处理数据时，我们是一个物品一个物品，一个一个体积的枚举。
因此我们可以不必开两个数组记录体积和价值，而是边输入边处理。
代码如下：
#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int f[N];
int main()
{
int n, m;
cin >> n >> m;
for(int i = 1; i <= n; i++) {
int v, w;
cin >> v >> w; // 边输入边处理
for(int j = m; j >= v; j--)
f[j] = max(f[j], f[j - v] + w);
}
cout << f[m] << endl;
return 0;
}
3. 代码实现
#include <bits/stdc++.h>
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 = m; j >= v[i]; j --)
f[j] = max(f[j], f[j - v[i]] + w[i]);
cout << f[m] << endl;
return 0;
}
二、完全背包问题
1. 题目描述
有 N 种物品和一个容量是 V 的背包，每种物品都有无限件可用。
第 i i i 种物品的体积是 v i v_i vi，价值是 w i w_i wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。
输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。
接下来有 N 行，每行两个整数 v i , w i v_i,w_i vi,wi，用空格隔开，分别表示第 i i i 种物品的体积和价值。
输出格式
输出一个整数，表示最大价值。
数据范围
0
<
N
,
V
≤
1000
0<N,V≤1000
0<N,V≤1000
0
<
v
i
,
w
i
≤
1000
0<v_i,w_i≤1000
0<vi,wi≤1000
输入样例
4 5
1 2
2 4
3 4
4 5
输出样例：
10
2. 思路分析
版本一： 二维数组
状态变量：f[i][j] 表示前
i
i
i 件物品放入容量为
j
j
j 的背包的最大价值。
当前背包容量为 j j j，我们要考虑 i i i 件物品能否放入？是否放入？
-
当前背包容量
j < w[i]，不能放入，则f[i][j] = f[i - 1][j] -
当前背包容量
j > w[i]，能放入，但要考虑代价- 若第
i
i
i 件物品不放入背包，则
f[i][j] = f[i - 1][j] - 若第
i
i
i 件物品放入背包，则
f[i][j] = f[i][j - w[i]] + c[i]
- 若第
i
i
i 件物品不放入背包，则
对于前
i
i
i 件物品，背包容量为 j - w[i] 时可能已经放入了第
i
i
i 件物品，容量为
j
j
j 时还可以再放入第
i
i
i 件物品，所以用 f[i][j - w[i]] 更新 f[i][j]。
代码实现如下：
for (int i = 1; i <= n; i ++)
{
for (int j = 1; j <= m; j ++)
{
if (j < w[i])
f[i][j] = f[i - 1][j];
else
f[i][j] = max(f[i - 1][j], f[i][j - w[i]] + c[i]);
}
}
cout << f[n][m] << endl;
版本二： 一维数组
用一维数组 f[j] 只记录一行数据，让
j
j
j 值顺序循环，顺序更新 f[j]值。
for (int i = 1; i <= n; i ++)
{
for (int j = 1; j <= m; j ++)
{
if (j < w[i])
f[j] = f[j];
else
f[j] = max(f[j], [j - w[i]] + c[i]);
}
}
cout << f[m] << endl;
实际上，只有当枚举的背包容量 j>= v[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]);
3. 代码实现
#include <bits/stdc++.h>
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;
}
三、多重背包问题I
1. 题目描述
有 N 种物品和一个容量是 V 的背包。
第 i i i 种物品最多有 s i s_i si 件，每件体积是 v i v_i vi，价值是 w i w_i wi。
求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。
输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。
接下来有 N 行，每行三个整数 v i , w i , s i v_i,w_i,s_i vi,wi,si，用空格隔开，分别表示第 i i i 种物品的体积、价值和数量。
输出格式
输出一个整数，表示最大价值。
数据范围
0
<
N
,
V
≤
100
0<N,V≤100
0<N,V≤100
0
<
0<
0<v_i,w_i,s_i
≤
100
≤100
≤100
输入样例
4 5
1 2 3
2 4 1
3 4 3
4 5 2
输出样例：
10
2. 思路分析
01背包：第
i
i
i 种物品可以取0件、取1件。
多重背包：第
i
i
i 种物品可以取0件、取1件、取2件…取
s
i
s_i
si件。
多重背包问题转化为01背包求解：把第
i
i
i 种物品换成
s
i
s_i
si 件01背包中的物品，每件物品的体积为
k
∗
v
i
k * v_i
k∗vi，价值为
k
∗
w
i
k * w_i
k∗wi(0
≤
\leq
≤ k
≤
\leq
≤
s
i
s_i
si)
3. 代码实现
#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int n, m;
int v[N], w[N], s[N];
int f[N][N];
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i ++) cin >> v[i] >> w[i] >> s[i];
for (int i = 1; i <= n; i ++)
for (int j = 0; j <= m; j ++)
for (int k = 0; k <= s[i] && 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
}
四、多重背包问题 II
1. 题目描述
有 N 种物品和一个容量是 V 的背包。
第 i i i 种物品最多有 s i s_i si 件，每件体积是 v i v_i vi，价值是 w i w_i wi。
求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。
输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。
接下来有N 行，每行三个整数 v i , w i , s i v_i,w_i,s_i vi,wi,si，用空格隔开，分别表示第 i i i 种物品的体积、价值和数量。
输出格式
输出一个整数，表示最大价值。
数据范围
0
<
N
≤
1000
0<N≤1000
0<N≤1000
0
<
V
≤
2000
0<V≤2000
0<V≤2000
0
<
0<
0<v_i,w_i,s_i
≤
2000
≤2000
≤2000
提示：
本题考查多重背包的二进制优化方法。
输入样例
4 5
1 2 3
2 4 1
3 4 3
4 5 2
输出样例：
10
2. 思路分析
二进制优化方法的例子：
假设有50个苹果，现在要取
n
n
n 个苹果（
n
n
n
≤
\leq
≤ 50），如何取？朴素的作家应该是将苹果一个一个拿出来，知道
n
n
n 个苹果被取出来。
二进制优化的思想就是：再假设有5个苹果和6只箱子，利用箱子继续某些预备工作，可以在每个箱子中放 2 k 2^k 2k(k ≥ \geq ≥ 0)个苹果，也就是1、2、4、8、16、19（剩余的数），取任意 n n n 个苹果时，只需要推出几只箱子就可以了。例如：取20个苹果，只需要拿出2个箱子（1、19），这样的话原来20次操作的现在变成2次操作就可以了。
二进制拆分思想：
将第
i
i
i 种物品拆分成若干件物品，每件物品的体积和价值乘以一个拆分系数（1,
2
1
2^1
21,
2
2
2^2
22…
2
k
−
1
2^{k-1}
2k−1,
s
i
−
2
k
+
1
s_i - 2^k + 1
si−2k+1），就可以转化成01背包的物品求解。
例如： s i = 12 s_i = 12 si=12,拆分系数为 1 , 2 , 4 , 5 1,2,4,5 1,2,4,5，转化成4件01背包的物品： ( v i , w i ) (v_i, w_i) (vi,wi)、 ( 2 v i , 2 w i ) (2v_i, 2w_i) (2vi,2wi)、 ( 4 v i , 4 w i ) (4v_i, 4w_i) (4vi,4wi)、 ( 5 v i , 5 w i ) (5v_i, 5w_i) (5vi,5wi)
3. 代码实现
#include <bits/stdc++.h>
using namespace std;
//逐一枚举到最大是 N * logN
const int N = 12010, M = 2010;
int n, m;
int v[N], w[N], f[M];
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个
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. 题目描述
有 N 组物品和一个容量是 V 的背包。
每组物品有若干个，同一组内的物品最多只能选一个。
每件物品的体积是
v
i
j
v_{ij}
vij，价值是
w
i
j
w_{ij}
wij，其中
i
i
i 是组号，
j
j
j 是组内编号。
求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。
输出最大价值。
输入格式
第一行有两个整数 N，V，用空格隔开，分别表示物品组数和背包容量。
接下来有 N 组数据：
- 每组数据第一行有一个整数 S i S_i Si，表示第 i i i 个物品组的物品数量；
- 每组数据接下来有 S i S_i Si 行，每行有两个整数 v i j , w i j v_{ij},w_{ij} vij,wij，用空格隔开，分别表示第 i i i 个物品组的第 j j j 个物品的体积和价值；
输出格式
输出一个整数，表示最大价值。
数据范围
0
<
N
,
V
≤
100
0<N,V≤100
0<N,V≤100
0
<
S
i
≤
100
0<S_i≤100
0<Si≤100
$0<
v
i
j
,
w
i
j
v_{ij},w_{ij}
vij,wij≤100$
输入样例
3 5
2
1 2
2 4
1
3 4
1
4 5
输出样例：
8
2. 思路分析
最大价值应该是物品组
i
i
i 和背包容量
j
j
j 的函数，用 f[i][j] 表示前
i
i
i 组物品，能放入容量为
j
j
j 的背包的最大价值。
朴素算法应该是循环物品组，循环背包容量，对第 i i i 组物品，容量为 j j j 的背包，有 s + 1 s + 1 s+1 种选法，
max(f[i - 1][j], f[i - 1][j - v 1 v_1 v1] + w 1 w_1 w1, f[i - 1][j - v 2 v_2 v2] + w 2 w_2 w2,…,f[i - 1][j - v 5 v_5 v5] + w 5 w_5 w5)
代码如下：
// 背包问题，朴素算法
for (int i = 1; i <= n; i ++) //物品
for (int j = 1; j <= m; j ++) //体积
for (int k = 0; k < s[i]; k ++) //决策
if (v[i][k] <= j)
f[i][j] = max(f[i][j], f[i - 1][j - v[i][k]] + w[i][k]);
cout << f[n][m] << endl;
可以优化为一维数组：文章来源：https://www.toymoban.com/news/detail-420805.html
for (int i = 1; i <= n; i ++) //物品
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;
3. 代码实现
#include <bits/stdc++.h>
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 ++) //物品
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;
}
创作不易，如果有帮助到你，请给文章点个赞和收藏，让更多的人看到！！！
关注博主不迷路，内容持续更新中。文章来源地址https://www.toymoban.com/news/detail-420805.html
到了这里，关于算法基础复盘笔记Day09【动态规划】—— 背包问题的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
