AcWing 12. 背包问题求具体方案
原题链接
中等
作者:
fancywing
,
2021-01-19 11:50:30
,
所有人可见
,
阅读 392
C++ 代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int v[N], w[N], f[N][N];
int main(){
int n,m;
cin>>n>>m;
for(int i = 1; i <= n; i++) cin>>v[i]>>w[i];
// 要求是字典序,所以改成由上往下循环
for(int i = n; i>=1; i--){
for(int j = 0; j <= m; j++){
f[i][j] = f[i + 1][j];
if(j >= v[i]) f[i][j] = max(f[i][j], f[i + 1][j-v[i]] + w[i]);
}
}
// 最大值是f[1][m]
int j = m;
for(int i = 1; i <= n; i++){
if(j >= v[i] && f[i][j] == f[i+1][j-v[i]]+w[i]){
cout<<i<<' ';
j -= v[i];
}
}
return 0;
}