本文主要是介绍动态规划——采矿的小奇【集训笔记】,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
假期小奇去采矿场体验生活,工头为每个员工发放了一个最多能装 M 公斤的背包,经过一天的辛苦小奇开采出了 n 块矿石,它们的重量分别是W1,W2,...,Wn,经过预估它们的价值分别为C1,C2,...,Cn,那么请你帮助小奇计算他能获得最大总价值是多少。
第一行:两个整数,M(背包容量,M≤200)和N(矿石数量,N≤30);
第2..N+1行:每行二个整数Wi,Ci,表示每块矿石的重量和价值。
仅一行,一个数,表示最大总价值
2 1
3 3
4 5
7 9
#include<iostream>
using namespace std;
#define MAXX 31
int c[MAXX],v[MAXX],f[MAXX][201];
int main(){int m,n;cin>>m>>n;for(int i=1;i<=n;i++){cin>>c[i]>>v[i];}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(j<c[i]) {f[i][j]=f[i-1][j];}else {f[i][j]=f[i-1][j]>f[i-1][j-c[i]]+v[i]?f[i-1][j]:f[i-1][j-c[i]]+v[i];}}}cout<<f[n][m];return 0;
}
对于1318的这种情况:
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(j<c[i]) {
f[i][j]=f[i-1][j];
}else {
f[i][j]=f[i-1][j]>f[i-1][j-c[i]]+v[i]?f[i-1][j]:f[i-1][j-c[i]]+v[i];
}
}
}
无:
}else {
f[i][j]=f[i-1][j]>f[i-1][j-c[i]]+v[i]?f[i-1][j]:f[i-1][j-c[i]]+v[i];
}
会偏小
为什么?
举个例子:
n=4,m=6
物品:3 2
物品:4 5
物品:5 3
物品:1 4
状态转移方程表 ‼
0 0 2 2 2 2
0 0 0❌(2) 5 5 5
所以要加上
}else {
f[i][j]=f[i-1][j]>f[i-1][j-c[i]]+v[i]?f[i-1][j]:f[i-1][j-c[i]]+v[i];
}
逆序:
0 0 2 2 2 2
0 0 2 5 5 5
(从右向左推)
顺序:
0 0 2 2 2 2
0 0 2 5 5 5
(从左向右推)
顺序逆序对二维矩阵不影响
滚动数组(变量)
第一行:a数组存储(原)
第二行:b数组存储(原)
第三行:a数组存储(用a数组推出了原b数组,原a数组无用)(新)
第四行:b数组存储(用b数组推出了新a数组,原b数组无用)(新)
第N 行只依赖于第N-1 行,不依赖于其他行
继续压缩,将f数组定义为一维
#include<iostream>
#include<cstring>
using namespace std;
#define MAXX 31
int c[MAXX],v[MAXX],f[MAXX];
int main(){memset(f,0,sizeof(f));int m,n;cin>>m>>n;for(int i=1;i<=n;i++){cin>>c[i]>>v[i];}for(int i=1;i<=n;i++){for(int j=m;j>=c[i];j--){f[j]=f[j]>f[j-c[i]]+v[i]?f[j]:f[j-c[i]]+v[i];}}cout<<f[m];return 0;
}
这种方法j的遍历
必须逆序‼必须逆序‼
必须逆序‼必须逆序‼
必须逆序‼必须逆序‼
一个物品可以取N个
只要能装下就可以
如果把遍历变成顺序(当然,这在这道题里不行)
就成了完全背包的一维模板
0-1背包 问题中的物品不能无限次的重复取,
也就是只有一个
完全背包 问题中的物品有多个
空间复杂度:
O(NM)-------->O(2M)------>O(M)
0-1背包---->滚动数组--->亚完全背包
这篇关于动态规划——采矿的小奇【集训笔记】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!