求状态转移路径问题只能用二维数组做
本题为01背包求状态转移路径(本题还要求字典序输出,故逆序遍历)
二维01背包模板(与一维区别很大):
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]);
}
}
本题代码:
#include <iostream>
using namespace std;
const int N = 1010;
int n, m;
int w[N], v[N];
int f[N][N];
int path[N], cnt=0;
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 = 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]);
}
}
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])
{
path[cnt ++ ] = i;
j -= v[i];
}
}
for (int i = 0; i < cnt; ++ i)
cout << path[i] << " ";
}