思路分析

通过此题掌握背包问题求字典序最小的方法，就是反着枚举，使得最终目标是dp[1][m]， 这样求方案时再反推回来，在可选可不选的时候选，就可以得到字典序最小了

C++ 代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1010;

int v[N], w[N];
int dp[N][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)//为了字典序反着看 这样最终目标就是dp[1][m]
        for(int j = 0;j <= m;++j){
            dp[i][j] = dp[i+1][j];
            if(j >= v[i]) dp[i][j] = max(dp[i][j], dp[i+1][j-v[i]] + w[i]);
        }
    //下面是套路，只不过可选可不选的时候必选，因为字典序
    int i = 1, j = m;
    while(i <= n){
        if(j >= v[i] && dp[i][j] == dp[i+1][j-v[i]] + w[i]){
            cout << i << " ";
            j -= v[i];
            ++i;
        }else ++i;
    }

}