正序dp

正序也可以做，只需将数组倒着读入，可能更有助于理解

C++ 代码

#include <iostream>

using namespace std;

const int N = 1010;

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

int main()
{
    scanf("%d%d", &n, &m);

    // 注意将数组倒着读入，因为打印时最先被打印出来的是最后一个被dp的，
    // 也就是数组中的最后一个元素
    for (int i = n; i; --i) scanf("%d%d", &v[i], &w[i]);

    for (int i = 1; i <= n; ++i)
        for (int j = 0; j <= m; ++j)
            if (j < v[i]) f[i][j] = f[i - 1][j];
            else f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);

    int k = m;
    for (int i = n; i; --i)
        // 能选该元素就尽可能地选该元素，因为数组是倒序的，这样一定是字典序最小的
        if (k >= v[i] && f[i][k] == f[i - 1][k - v[i]] + w[i])
        {
            printf("%d ", n + 1 - i);
            k -= v[i];
        }

    return 0;
}