算法:这个题相当坑,坑点就在字典序,原本我写的算法是从n开始downto1,逐个枚举价值关系,但这样恰好是字典序相反的顺序.而从正面开做的话无从下手,于是我另辟蹊径,将f[][]完全颠倒,f[i][j]的含义:仅拿第i个和以后的物品,所产生的最大价值!这样正面枚举便迎刃而解.

C++ 代码

#include<iostream>
#include<algorithm>
using namespace std;

int n, m, i,j,v[1001], w[1001], a[1001],f[1002][1002];

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    cin >> n >> m;
    for (i = 1; i <= n; i++)cin >> v[i]>> w[i];
    for (i = n; i >0; i--)
        for (j = 1; j <= m; j++)
        {
            f[i][j] = f[i +1][j];
            if (j - v[i] >= 0 && f[i][j] < f[i + 1][j - v[i]] + w[i])
                f[i][j] = f[i + 1][j - v[i]] + w[i];
    }//镜像对称做法
    for (i = 1; i <= n; i++)
        if (f[i][m] == f[i + 1][m - v[i]] + w[i] && m>=v[i])//最后一组数据有一个m<v[i]的情况,这需要判断
        //如果选择拿走这个物品则:
        {
            cout << i << ' ';
            m -= v[i];
                if (m <= 0) return 0;
        }
    return 0;
}