python/C++专题课程/背包九讲/TestProject/9_ChangePackage.cpp

#include <bits/stdc++.h>

using namespace std;
/**
 *9. 背包问题的变化
    1）题目：
        输出01背包的具体方案
    2）输入：
        同01背包
 * @return
 */
#define maxV 1000
#define maxN 100

int main(void) {
    int cases, n, v, ci[maxN], wi;
    int f[maxV];
    bool g[maxN][maxV]; //g[i][v]=0 表示没放i时的f(i, v)较大，
    //g[i][v]=1 表示放进i时的f(i, v)较大
    freopen("../9.txt", "r", stdin);
    cin >> cases;
    while (cases--) {
        memset(f, 0, sizeof(f));
        memset(g, 0, sizeof(g));
        cin >> n >> v;
        for (int i = 0; i < n; i++) {
            cin >> ci[i] >> wi;
            for (int j = v; j >= 0; j--) {
                if (j >= ci[i]) {
                    if (f[j - ci[i]] + wi > f[j]) {
                        f[j] = f[j - ci[i]] + wi;
                        g[i][j] = 1;
                    }
                }
            }
        }

        int i = n - 1, j = v;
        while (i >= 0) {
            if (g[i][j] == 1) {
                cout << "选了" << i << endl;
                j -= ci[i];
            } else {
                cout << "没选" << i << endl;
            }
            i--;
        }
        cout << endl;
    }
}