Acwing 12. 背包问题求具体方案

Acwing 12. 背包问题求具体方案

01背包问题，但是要求输出 字典序最小的方案数 。

思路:

状态转移方程: \(f[i][j] = max(f[i - 1][j],f[i - 1][j - v[i]] + w[i])\)

求具体方案其实就是判断每个物品是否被选，求方案其实就是从 \(f[n,m]\) 倒推出来每一个 \(i\) 是否选择。

需要根据转移方程来判断是否选择第 \(i\) 个物品，所以不能滚动。

然后因为这里要求 字典序最小，所以采用贪心的策略。

然后对于第一个物品来说可能有三种情况

• 只能选——必选
• 只能不选——必不选
• 可选可不选——一定要选

显然求字典序最小的时候，我们需要优先考虑编号小的物品，但是找方案的时候，又是从 \(f[n,m]\) 开始回推的，所以我们在求解 \(01\) 背包的时候，从后往前推，就可以从 \(f[1,m]\) 开始往前推了，这样的话，就和求字典序最小的顺序一致了。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 5;
int f[N][N], n, m, w[N], v[N];
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d%d", &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] >= 0 && f[i][j] == f[i + 1][j - v[i]] + w[i])
        {
            printf("%d ", i);
            j -= v[i];
        }
    }
    return 0;
}