$\LARGE\color{orange}{刷题日记(算法提高课)}$

题目要求我们输出字典序最小的具体方案，我们从 $f[i][j]$ 的状态转移方程来考虑这个问题

观察 $f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i])$ 不难发现，$f[i][j]$ 的值只会从 $f[i-1][j]$ 和 $f[i-1][j-v[i]]+w[i]$ 转移过来

这会有三种可能，即：

• $f[i][j]$ 仅从 $f[i-1][j]$ 转移过来，说明 $f[i][j]=f[i-1][j],\ f[i][j]\ne f[i-1][j-v[i]]+w[i]$ ，此时不选择物品 $i$

• $f[i][j]$ 仅从 $f[i-1][j-v[i]]+w[i]$ 转移过来，说明 $f[i][j]=f[i-1][j-v[i]]+w[i],\ f[i][j]\ne f[i-1][j]$，此时选择物品 $i$

• $f[i][j]$ 都可以从这两个状态转移过来，说明 $f[i][j]=f[i-1][j]=f[i-1][j-v[i]]+w[i]$ ，此时物品 $i$ 可选可不选，但题目要求路径的字典序最小，因此我们需要将该编号输出

这里有一个问题是，为什么第三种情况输出物品编号才会满足字典序最小？

其实很简单，因为我们是从后往前考虑的，因此先输出的物品编号一定大于后输出的物品编号，由于我们的输出是反向的，因此考虑字典序需要从后往前考虑

如果输出当前编号的话，相比于不输出的情况，当前编号一定会小于之后输出的物品编号，因此可以保证字典序最小

因此在判断具体路径时，我们从后往前依次判断当前的 $f[i][j]$ 可以从哪个状态转移过来，只要当前状态的值可以从选择物品 $i$ 的状态转移过来，那么我们便输出该物品编号

正如上面所说，这样输出的字典序是反向的，因此我们在背包遍历的时候从后往前遍历，这样 $f[1][m]$ 就变成了最终的答案，我们再从这个状态反推回去即可

完整代码：

#include <iostream>

using namespace std;

const int N = 1010;

int f[N][N], v[N], w[N];
int n, m;

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 = 1; 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]);
        }

    //f[1][m]为最终答案

    int k = m;

    for(int i = 1; i <= n; i++)
        if(k - v[i] >= 0 && f[i][k] == f[i + 1][k - v[i]] + w[i])
        {
            cout << i << " ";
            k -= v[i];
        }

    return 0;
}