假期小奇去采矿场体验生活，工头为每个员工发放了一个最多能装?M 公斤的背包，经过一天的辛苦小奇开采出了 n 块矿石，它们的重量分别是W1，W2，...,Wn,经过预估它们的价值分别为C1,C2,...,Cn，那么请你帮助小奇计算他能获得最大总价值是多少。
第一行：两个整数，M(背包容量，M≤200)和N(矿石数量，N≤30)；
第2..N+1行：每行二个整数Wi，Ci，表示每块矿石的重量和价值。
?
仅一行，一个数，表示最大总价值
#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背包---->滚动数组--->亚完全背包
?