AcWing 12. 背包问题求具体方案
原题链接
中等
作者:
大鼻孔
,
2022-04-19 10:17:17
,
所有人可见
,
阅读 305
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
struct Node{
int W;
vector<int> v;
void push(int x){v.push_back(x);}
void out(){
for(int i=0;i<v.size();i++) cout<<v[i]<<" ";
cout<<endl;
}
};
const int N=1e5+10;
Node f[N];
int n,m;
int v[N],w[N];
int main()
{
ios::sync_with_stdio(false);
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
for(int i=1;i<=n;i++){
f[i]=f[i-1];
for(int j=m;j>=v[i];j--)
{
Node k=f[j-v[i]];
if(f[j].W<k.W+w[i])
{
f[j].W=k.W+w[i];
f[j].v=k.v;
f[j].push(i);
}
}
}
f[m].out();
return 0;
}