背包九讲之多重背包，二维数组

multiple_pack-1.cpp

/*
 * 背包九讲之多重背包 二维数组
 *  from: http://acm.hdu.edu.cn/showproblem.php?pid=2191
 *  reference: https://blog.csdn.net/hellobabygogo3/article/details/7993547
 */

#include <bits/stdc++.h>

using namespace std;

void complete_pack(int *d[], int i, int V, int P, int H) {
    int tmp;

    for (int j = 1; j <= V; j++) {
        if (j >= P) {
            tmp = d[i][j-P] + H;
            d[i][j] = (d[i-1][j] > tmp) ? d[i-1][j] : tmp;
        } else {
            d[i][j] = d[i-1][j];
        }
    }
}

void zero_one_pack(int *d[], int i, int V, int P[], int H[], int C[]) {
    int tmp;

    for (int j = 1; j <= V; j++) {
        d[i][j] = d[i-1][j];

        /*
         * 把M件物品A拆成M种物品A，每种物品是一样的
         * h优化：拆成2的幂次方种物品，每种一件。对于这种，二维数组无法使用，因为是不同的物品
         */
        for (int k = 1; (k <= C[i-1]) && (j >= k*P[i-1]); k++) {
            tmp = d[i-1][j-k*P[i-1]] + k*H[i-1];
            d[i][j] = (d[i][j] > tmp) ? d[i][j] : tmp;
        }
    }
}

// d[i][v] = max{ d[i-1][v], d[i-1][v-k*C[i]]+k*W[i] }
int multiple_pack(int P[], int H[], int C[], int N, int V) {
    int **d = new int *[N+1];

    for (int i = 0; i <= N; i++) {
        d[i] = new int[V+1];
        memset(d[i], 0, sizeof(int)*(V+1));
    }

    for (int i = 1; i <= N; i++) {
        if (P[i-1]*C[i-1] > V) {
            complete_pack(d, i, V, P[i-1], H[i-1]);
        } else {
            zero_one_pack(d, i, V, P, H, C);
        }
    }

    return d[N][V];
}

int main() {
    int C, n, m;
    int *p, *h, *c;
    cin >> C;

    while (C--) {
        cin >> n >> m;

        p = new int[m];
        h = new int[m];
        c = new int[m];

        for (int i = 0; i < m; i++)
            cin >> p[i] >> h[i] >> c[i];

        cout << multiple_pack(p, h, c, m, n) << endl;

        delete p, h, c;
    }

    return 0;
}