AcWing 12. 背包问题求具体方案
原题链接
中等
作者:
wngzs
,
2022-07-12 14:21:29
,
所有人可见
,
阅读 137
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int f[N][N],w[N],v[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=1;j<=m;j++)
{
//从前i个和i+1个中,判断选不选第i个物品取得的最大值
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]);
}
}
//用t代表变化的体积
int j=m;
for(int i=1;i<=n;i++)
{
//如果选上第i个物品时的价值是和最大价值是匹配的,就选上他。
if(j>=v[i]&&f[i][j]==f[i+1][j-v[i]]+w[i]){
cout<<i<<' ';
j-=v[i];
}
}
}