AcWing 12. 背包问题求具体方案 一维dp优化(bushi)
原题链接
中等
作者:
leimingze
,
2022-02-27 01:59:25
,
所有人可见
,
阅读 493
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int v[N], w[N];
int n, m;
int f[N];
int path[N], cnt;
int g[N][N];
int main()
{
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 = m; j >= v[i]; j--)
if(f[j]<=f[j-v[i]]+w[i])
{
f[j]=f[j-v[i]]+w[i];
g[i][j]=1;
}
for (int i = 1, j = m; i <= n; i++)
{
if (j >= v[i] && g[i][j])
{
path[cnt++] = i;
j -= v[i];
}
}
for (int i = 0; i < cnt; i++)cout << path[i] << ' ';
return 0;
}
非得要记录下来第一次的序号,是不是太累了,还是yxc的改变枚举顺序方便些。我们就懂了原来dp可以通过改变枚举序来完成,不是一定要从小到大,从上到下,从左到右的,填表无定法。
Orz
orz