python/C++专题课程/背包九讲/TestProject/3_multiplexPackage.cpp

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

#define maxV 1000
int f[maxV], v;
/*
 3. 多重背包
    1）题目：
    有n种物品和一个容量为v的背包。
    第i种物品最多有n[i]件可用，每件费用是c[i]，价值是w[i]。
    求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
2）输入：
    测试用例数
    物品数 背包容量
    n个物品的ni ci wi
 * */
void ZeroOnePack(int ci, int wi) {
    for (int j = v; j >= 0; j--)
        if (j >= ci)
            f[j] = max(f[j], f[j - ci] + wi);
}

void CompletePack(int ci, int wi) {
    for (int j = 0; j <= v; j++)
        if (j >= ci)
            f[j] = max(f[j], f[j - ci] + wi);
}

void MultiplePack(int ni, int ci, int wi) {
    if (ni * ci >= v) {
        CompletePack(ci, wi);
        return;
    }
    int k = 1, amount = ni;
    while (k < ni) {
        ZeroOnePack(ci * k, wi * k);
        amount -= k;
        k *= 2;
    }
    ZeroOnePack(ci * amount, wi * amount);
}

int main(void) {
    int cases, n, ni, ci, wi;
    freopen("../3.txt", "r", stdin);
    cin >> cases;
    while (cases--) {
        memset(f, 0, sizeof(f));
        cin >> n >> v;
        for (int i = 0; i < n; i++) {
            cin >> ni >> ci >> wi;
            MultiplePack(ni, ci, wi);
        }
        //for (int i = 0; i <= v; i++) cout << f[i] << " "; cout << endl;
        cout << f[v] << endl;
    }
    return 0;
}