动态规划——采矿的小奇【集训笔记】

题目描述

假期小奇去采矿场体验生活，工头为每个员工发放了一个最多能装 M 公斤的背包，经过一天的辛苦小奇开采出了 n 块矿石，它们的重量分别是W1，W2，...,Wn,经过预估它们的价值分别为C1,C2,...,Cn，那么请你帮助小奇计算他能获得最大总价值是多少。

输入

第一行：两个整数，M(背包容量，M≤200)和N(矿石数量，N≤30)；
第2..N+1行：每行二个整数Wi，Ci，表示每块矿石的重量和价值。
 

输出

仅一行，一个数，表示最大总价值

样例输入1

10 4
2 1
3 3
4 5
7 9

样例输出1

12

提示/说明

标签

普及 其他 背包

#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背包---->滚动数组--->亚完全背包