bp题型
用f[i][j]表示取到第i个时,再背包体积为j时能取到的最大值
- 二维数组版
#include <iostream>
using namespace std;
int n,m;
const int N =1010;
int v[N],w[N];
int f[N][N];
int main(){
cin >> n >> m;
for(int i = 1 ; i <= n ; i++ ) //从1开始存,因为下面要用到f[i-1][j],避免数组溢出
cin >> v[i] >> w[i];
for(int i = 1 ; i <= n ; i++){
for(int j = 1; j <= m ;j ++){
f[i][j] = f[i-1][j]; //先将不去第i个时的最大值赋值给f[i][j]
if(j >= v[i]){ //当V可以直接装下我们就要去通过对比不取i和取i后的值来更新f[i][j]
f[i][j] = max(f[i][j],f[i - 1][j - v[i]] + w[i]);
}
}
}
cout << f[n][m] << endl;
return 0;
}
优化版
优化为一维数组
#include <iostream>
using namespace std;
int n, m;
const int N = 1010;
int v[N],w[N];
int f[N];
int main(){
cin >> n >> m;
for(int i = 1 ; i< n ; i++){
cin >> v[i] >> w[i];
}
for(int i = 1; i <= n ; i++){
for(int j = m ; j >= v[i] ; j--){
f[j] = max(f[j],f[j-v[i]+w[i]);
}
}
cout << f[m] << endl;
return 0;
}