题解 | 【模板】01背包（方案输出） #

$[模板+背包]$

背包问题中输出最大价值的任意一种方案

$dp[i]$ 表示：容量为 $i$ 的背包能够装到的最大价值

$use[i][j]$ 表示：当考虑完前 $i$ 个物品后，当背包容量为 $j$ 时所装的最大价值，第 $i$ 个物品是否必须使用 $(true \ or\ false)$

这里是小于符号，而不是小于等于符号。小于符号表示这有更优的方案转移而来，而如果等于，那么可能可以从另外一种等价的方案转移而来，那么会导致记录 $use[i][j]$ 成为不必须，造成混乱。

if(dp[j] < dp[j - v[i]] + w[i]){
    dp[j] = dp[j - v[i]] + w[i];
    use[i][j] = true;
}

$cur$ 记录当前背包容积，因为我们是正序从 $1$ 到 $n$ 考虑物品的，所以 $use$ 得反过来从 $n$ 到 $1$ 逆序回溯

int cur = m; for(int i = n; i >= 1 && cur >= 0; i --)

$reverse$ 的作用是翻转所选物品顺寻，因为从 $n$ 到 $1$ 逆序回溯，所以所选物品是倒着开始选择的

reverse(res.begin(), res.end());

总代码：

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

#define endl '\n'
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define HelloWorld IOS;


void solve(){
    int n, m; cin >> n >> m;
    vector<int> v(n + 1), w(n + 1), dp(m + 1);
    vector<vector<bool> > use(n + 1, vector<bool> (m + 1));
    for(int i = 1; i <= n; i ++) cin >> v[i] >> w[i];

    for(int i = 1; i <= n; i ++){
        for(int j = m; j >= v[i]; j --){
            if(dp[j] < dp[j - v[i]] + w[i]){
                dp[j] = dp[j - v[i]] + w[i];
                use[i][j] = true;
            }
        }
    }
    vector<int> res;
    int cur = m;
    for(int i = n; i >= 1 && cur >= 0; i --){
        if(use[i][cur]){
            res.push_back(i);
            cur -= v[i];
        }
    }
    reverse(res.begin(), res.end());
    cout << (int)res.size() << endl;
    for(int e : res) cout << e << " ";
    cout << endl;
}
signed main(){
    HelloWorld;
    
    int tt; cin >> tt;
    while(tt --) solve();
    return 0;
}