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

[模板]01背包（方案输出）

代表考虑前种物品，物品总体积为的前提下能带走的最大物品价值。

通过动态规划得出最优解之后逆序去找每个物品是否应该被选取。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll NEG_INF = - (4000000000000000000LL);

void solve(int testcase) {
    ll n, m;
    cin >> n >> m;
    vector<pair<ll, ll>> items(n);
    for (auto &[w, v] : items) {
        cin >> w >> v;
    }

    vector<vector<ll>> dp(n + 1, vector<ll>(m + 1, NEG_INF));
    dp[0][0] = 0;
    for (ll i = 1; i <= n; ++i) {
        ll w = items[i - 1].first;
        ll v = items[i - 1].second;
        for (ll j = 0; j <= m; ++j) {
            dp[i][j] = dp[i - 1][j];
        }
        for (ll j = m; j >= w; --j) {
            if (dp[i - 1][j - w] != NEG_INF) {
                dp[i][j] = max(dp[i][j], dp[i - 1][j - w] + v);
            }
        }
    }

    ll maxV = 0;
    ll maxW = -1;
    for (ll j = m; j >= 0; --j) {
        if (dp[n][j] > maxV) {
            maxV = dp[n][j];
            maxW = j;
        }
    }

    vector<ll> res;
    ll curW = maxW;
    ll curV = maxV;
    for (ll i = n; i >= 1; --i) {
        ll w = items[i - 1].first;
        ll v = items[i - 1].second;
        if (curW >= w && dp[i - 1][curW - w] != NEG_INF && dp[i - 1][curW - w] + v == curV) {
            res.push_back(i);
            curW -= w;
            curV -= v;
        }
    }

    int k = res.size();
    cout << k << "\n";
    for (int i = k - 1; i >= 0; --i){
        cout << res[i] << " \n"[i == 0];
    }
    
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int T;
    cin >> T;
    for (int t = 0; t < T; t++) {
        solve(t);
    }
    return 0;
}