AcWing 12. 背包问题求具体方案
原题链接
中等
作者:
妙WA草
,
2022-07-04 16:33:18
,
所有人可见
,
阅读 182
题目描述
背包问题求具体方案
C++ 代码
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int n,m,f[1010][1010],v[1010],w[1010];
void dfs(int x,int y)
{
if(!x)return ;
if(y >= v[x] && f[x][y] == f[x - 1][y - v[x]] + w[x])//如果这个用过,输出编号继续往前找
{
cout << n - x + 1 << " ";
dfs(x - 1,y - v[x]);
return;
}
else
dfs(x - 1, y);//没用过,跳过这个往前找
}
int main()
{
cin >> n >> m;
for(int i = n; i > 0; i --)cin >> v[i] >> w[i];
//倒着读入,使最后一次判断的是第一个物品,便于回溯时字典序最小
//01背包
for(int i = 1; i <= n; 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]);
}
dfs(n,m);//回溯找哪些被用过了
}