题目描述

其他题解已经写得很详细了 就分享一下不用改变背包逻辑的写法

因为方案输出需要从后往前推，最先遇到的可选物品不一定是index最小的，所以普通贪心行不通。但如果输入数据的时候倒着来，倒推的时候最先遇到的就会是原本index最小的啦 最后只需要输出答案的时候把index调整过来（详见代码）这样写的好处就是背包部分的代码完全不用变

C++ 代码

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(){
    int n, m;
    cin >> n >> m;
    vector<vector<int>>dp(n + 1, vector<int>(m + 1, 0));
    int  v, w;
    vector<int>vol(n + 1, 0);
    vector<int>val(n + 1, 0);

    //倒着输入数据， 这样倒推的时候就会先处理到index小的
    for(int i = n; i >= 1 ; i--){
        cin >> vol[i] >> val[i];
    }

    for(int i = 1; i <=n ; i++){
        for(int j = 1; j <= m; j++){
            dp[i][j] = dp[i - 1][j];
            if(j >= vol[i]) dp[i][j] = max(dp[i][j], dp[i - 1][j - vol[i]] + val[i]);
        }
    }
    vector<int>res;
    int j = m;

    for(int i = n; i >= 1; i--){
        if(j >= vol[i] && dp[i][j] == dp[i - 1][j - vol[i]] +val[i]){
            //输出答案的时候再还原index
            res.push_back(n - i + 1);
            j -=  vol[i];
        }
    }
    for(auto n: res) cout << n << " ";
    cout << endl;



    return 0;
}