python/C++专题课程/背包九讲/TestProject/5_TwoDimensionPackage.cpp

#include <bits/stdc++.h>

using namespace std;
/**
 * 5. 二维费用的背包
    1）问题：
        对于每件物品，具有两种不同的费用；
        选择这件物品必须同时付出这两种代价；
        对于每种代价都有一个可付出的最大值（背包容量）。
        问怎样选择物品可以得到最大的价值。
        第i件物品所需的两种代价分别为a[i]和b[i]。
        两种代价可付出的最大值（两种背包容量）分别为V和U。物品的价值为w[i]。
    2）输入：
        测试用例数
        物品数 第一个背包容量v 第二个背包容量u
        第i个物品的ai bi wi
 */
#define maxV 1000
#define maxU 1000

int main(void) {
    int cases, n, v, u, ai, bi, wi;
    int f[maxV][maxU];
    freopen("../5.txt", "r", stdin);
    cin >> cases;
    while (cases--) {
        memset(f, 0, sizeof(f));
        cin >> n >> v >> u;
        for (int i = 0; i < n; i++) {
            cin >> ai >> bi >> wi;
            for (int j = v; j >= 0; j--) {
                for (int k = u; k >= 0; k--) {
                    if (ai <= j && bi <= k)
                        f[j][k] = max(f[j][k], f[j - ai][k - bi] + wi);
                }
            }
        }
//        for (int i = 0; i <= v; i++)
//            for(int j=0;j<=u;j++)
//                cout << f[i][j] << " ";
//            cout << endl;
        cout << f[v][u] << endl;
    }
}