房屋平面设计软件手机版,东莞整站优化推广公司找火速,电商类网站开发定制,外贸网站建设视频教程题目描述 假期小奇去采矿场体验生活#xff0c;工头为每个员工发放了一个最多能装 M 公斤的背包#xff0c;经过一天的辛苦小奇开采出了 n 块矿石#xff0c;它们的重量分别是W1#xff0c;W2#xff0c;...,Wn,经过预估它们的价值分别为C1,C2,...,Cn#xff0c;那么请你… 题目描述 假期小奇去采矿场体验生活工头为每个员工发放了一个最多能装 M 公斤的背包经过一天的辛苦小奇开采出了 n 块矿石它们的重量分别是W1W2...,Wn,经过预估它们的价值分别为C1,C2,...,Cn那么请你帮助小奇计算他能获得最大总价值是多少。 输入 第一行两个整数M(背包容量M≤200)和N(矿石数量N≤30) 第2..N1行每行二个整数WiCi表示每块矿石的重量和价值。 输出 仅一行一个数表示最大总价值 样例输入1 10 4 2 1 3 3 4 5 7 9 样例输出1 12 提示/说明 标签 普及 其他 背包 #includeiostream
using namespace std;
#define MAXX 31
int c[MAXX],v[MAXX],f[MAXX][201];
int main(){int m,n;cinmn;for(int i1;in;i){cinc[i]v[i];}for(int i1;in;i){for(int j1;jm;j){if(jc[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];}}}coutf[n][m];return 0;
} 对于1318的这种情况 for(int i1;in;i){ for(int j1;jm;j){ if(jc[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]; } 会偏小 为什么 举个例子 n4,m6 物品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数组定义为一维 #includeiostream
#includecstring
using namespace std;
#define MAXX 31
int c[MAXX],v[MAXX],f[MAXX];
int main(){memset(f,0,sizeof(f));int m,n;cinmn;for(int i1;in;i){cinc[i]v[i];}for(int i1;in;i){for(int jm;jc[i];j--){f[j]f[j]f[j-c[i]]v[i]?f[j]:f[j-c[i]]v[i];}}coutf[m];return 0;
} 这种方法j的遍历 必须逆序‼必须逆序‼ 必须逆序‼必须逆序‼ 必须逆序‼必须逆序‼ 一个物品可以取N个 只要能装下就可以 如果把遍历变成顺序当然这在这道题里不行 就成了完全背包的一维模板 0-1背包 问题中的物品不能无限次的重复取 也就是只有一个 完全背包 问题中的物品有多个 空间复杂度 O(NM)--------O(2M)------O(M) 0-1背包----滚动数组---亚完全背包
