DP 动态规划(一) ——背包问题 学习总结（闫氏DP分析法）
AcWing 2. 01背包问题AcWing 3. 完全背包问题AcWing 4. 多重背包问题AcWing 5. 多重背包问题AcWing 9. 分组背包问题
·
目录
前言
欢迎关注我的专栏,准备写完算法基础所有题解🚀🚀🚀 专栏链接
🌟一、了解动态规划DP
指的是将一个复杂的问题，分解成简单的问题（用一种递归的方式）——WIKI
本质：分治（与递归没有本质区别）+ 最优解 ，很多就是一些细节的不同。
🌟二、闫式DP分析法
y总的方法
🌟三、01背包 [DP入门]
[0-1]背包最基础动态规划，也是所以背包问题的基础，特点是：每种物品仅有一件，可以选择放或不放。
题目链接
题目
闫式DP分析
①状态表示
- 集合
f[i][j]:所有只从前i个物品中选,并且总体积≤j的选法的 【核心】请记住这句话，DP就是一直围绕这句话实现的 - 属性：MAX
②状态计算
- 当前背包容量不够
（j < v[i]），没得选，因此前i个物品最优解即为前i−1个物品最优解：f[i][j] = f[i - 1][j]。 - 如果可以选 ：
f[i][j] = f[i - 1][j - v[i]] + w[i]。
③二维分析过程↓
就第一步举例：首先对
f(4,8)的理解，其中4是指第i个物品就行选择（选 or不选），8是指背包的容量，看图，下一步是f(3,x)表示是对第4个物品进行了抉择（不管选还是不选4必须减去1）， 如果选择的话，背包容量就会减去第i个物品的体积 （表示当前背包容量）， 后面加上的第i物品价值+w[i], 图中的+8，就是现在背包的价值.。
代码
二维写法
时间复杂度 O(n*m)
#include <iostream>
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];//v:体积 w：价值
int f[N][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 = 1; j <= m; j ++) {
f[i][j] = f[i - 1][j];
if (j >= v[i]) {
f[i][j] =max (f[i][j],f[i - 1][j - v[i]] + w[i]);
}
}
}
cout << f[n][m] << endl;
return 0;
}
一维写法 [优化：对代码等价变形]
优化↓
for (int i = 1; i <= n; i ++) {
//for (int j = 1; j <= m; j ++) { 更改顺序
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[i][j] = max(f[j], f[j - 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]);
}
}
终极版本
#include <iostream>
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];//v:体积 w：价值
int f[N];//集合表示 一开始全为0
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;
}
🌟四、完全背包
-
与
[0-1]背包的区别 ——每件物品可以选无限次
题目链接题目
闫式DP分析
先从朴素(baoli)算法 时间复杂度接近 O(n3)
优化：错位相减的思路↓
- 图中橘色部分与
f[i,j-v]相差w - 得到：
f[i][j]=max(f[i-1][j],f[i,j-v]+w )完全背包 - 对比 ：
f[i][j]=max(f[i][j],f[i,j-v]+w )01背包
最终代码
#include <iostream>
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];//v:体积 w：价值
int f[N];//集合表示 一开始全为0
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;
}
🌟五、多重背包
- 与完全背包有点相似 —— 每件物品最多有 s[i]种选择
题目链接
朴素做法
#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++) { //枚举第i个物品选多少个
//个数限制 体积限制
f[i][j] = max(f[i][j], f[i - 1][j - v[i] * k] + w[i] * k);
}
}
}
cout << f[n][m] << endl;
return 0;
}
优化
用前面错位相减的思路 这道题用不了
- 如果一件一件选的话，暴力时间复杂度：O(n3) 而且数据类型还是1000 + 一定会TLE
所以，考虑二进制优化—> 优化后时间复杂度 : O(nlogn) - 步骤 ：拆分第i件物品分成若干件物品，其中每件物品有一个系数，这件物品的费用和价值均是原来的费用和价值乘以这个系数。使这些系数分别为1,2,4,…,2(k) , s[i]-2k+1 + 1.
(C)[下图的C]，且k是满足s[i] - 2k+1 + 1>0 的最大整数,并且C < 2k+1。
举个栗子，如果s[i]为13，就将这种物品分成系数分别为1,2,4,6(C)的四件物品。
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 25000;//2000 * log2 1000
int n, m;
int v[N], w[N];
int f[N];
int cnt = 0;//记录物品编号
int main () {
cin >> n >> m;
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 *= 2; //二进制优化
}
if (s >0) {//补上最后的C
cnt++;
v[cnt] = a * s;
w[cnt] = b * s;
}
}
n = cnt; //更新n
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;
}
🌟六、分组背包问题
- 与前面的背包的区别 ——前面背包都是每件物品选几次，而分组背包问题是第
i组物品选哪个？
题目
题目链接
思路
把分组背包问题 化解为 01背包问题
AC代码
- 朴素做法
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 110;
int s[N], f[N][N], v[N][N], w[N][N];
int n, V;
int main () {
cin >> n >> V;
for (int i = 1; i <= n; i ++ ) {
cin >> s[i];
for(int j = 1; j <= s[i]; j ++) {
cin >> v[i][j] >> w[i][j];
}
}
f[0][0] = 0;
for (int i = 1; i <= n; i ++ ) {
for(int j = V; j >= 0; j --) {
f[i][j] = f[i - 1][j];
for(int k = 1; k <= s[i]; k ++) {
if(j >= v[i][k])
f[i][j] = max(f[i][j], f[i - 1][j - v[i][k]] + w[i][k]);
}
}
}
cout << f[n][V] << endl;
return 0;
}
- 优化为一维
#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int n, m;
int v[N][N], w[N][N],s[N];//s：每组物品个数
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 ++) { // 枚举每一组物品 s
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;
}
🌟七、个人总结
01背包 & 完全背包
-
原式：
[01]f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i])
完全背包f[i][j] = max(f[i][j], f[i][j - v[i]] + w[i]); -
一维：
f[j] = max(f[j], f[j - v[i]] + w[i])[相同]
for(int i = 1; i <= n; i++) {
for(int j = m; j >= v[i]; j --) { //01背包
// for(int j = v[i]; j <= m; j --) { //完全背包
f[j] = max(f[j], f[j - v[i]] + w[i]);
}
}
- 为什么01背包 按照V…0 逆序，而完全背包于此相反？
如果转移的时候用的是上一层i - 1的状态的话，就从大到小来枚举体积[可以保证我们算体积 所用到的体积都是没有被计算过的 ] 即要保证第i次循环中的状态f[i][v]是由状态f[i-1][v-c[i]]递推而来的。。如果是本层i的状态的话（完全背包），于此相反就要从小到大来枚举体积【因为完全背包：每种物品可选无限件，考虑选第i件物品的时候，却正需要一个可能已选入第i种物品的子结果f[i][j-v[i]]】。
多重背包&多组背包
- 多重背包：采用二进制优化为01背包问题
- 多组背包：多了枚举每一组物品，从而转化为01背包问题
🌟 八、文章参考
🌟 九、最后
分享一段学习中看到的快乐
感谢你能看完， 如有错误欢迎评论指正，有好的思路可以交流一波，如果对你有帮助的话，点个赞鼓励下🌹🌹🌹
纵情码海钱塘涌，杭州开发者创新动！ 属于杭州的开发者社区！致力于为杭州地区的开发者提供学习、合作和成长的机会；同时也为企业交流招聘提供舞台！
更多推荐
61
0- 0
已为社区贡献1条内容
所有评论(0)