题目描述
有 N 种物品和一个容量是 V 的背包,每种物品都有无限件可用。
第 i 种物品的体积是 vi,价值是 wi。
求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。
输出最大价值。
样例
1.01背包问题 状态方程:f[i][j] = max(f[i][j], f[i-1][j-v]+w)
2.完全背包问题 状态方程:f[i][j] = max(f[i][j], f[i][j-v]+w)
C++ 代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int n,v;
int M[N],V[N];
int f[N][N];
int main(){
cin>>n>>v;
for(int i=1;i<=n;i++){
cin>>M[i]>>V[i];
}
for(int i=1;i<=n;i++){
for(int j=0;j<=v;j++){
f[i][j] = f[i-1][j];
if(j>=M[i]) f[i][j] = max(f[i][j], f[i][j-M[i]] + V[i]);//完全背包问题状态更新方程是其推理方程的等价变形
}
}
cout<<f[n][v]<<endl;
return 0;
}
//空间优化后
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int n,v;
int M[N],V[N];
int f[N];
int main(){
cin>>n>>v;
for(int i=1;i<=n;i++){
cin>>M[i]>>V[i];
}
for(int i=1;i<=n;i++){
for(int j=M[i];j<=v;j++){//从M[i]进行循环即可,更改初始化
f[j] = max(f[j],f[j-M[i]]+V[i]);
//f[j] = f[j];
//空间优化:f[i][j] = f[i-1][j],右边f[j]没有更新,为i-1层的值,故等价
//if(j>=M[i]) f[j] = max(f[j], f[j-M[i]] + V[i]);
//因为j-M[i]必然小于j,而j的值从小到大进行循环,故f[j-M[i]]的值为第i层的值,等价于原试
//故可进行代码变形。
}
}
cout<<f[v]<<endl;
return 0;
}