背包九讲之多重背包 一维数组

multiple_pack-2.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 V, int P, int H) {
    int tmp;

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

void zero_one_pack(int *d, int V, int P, int H) {
    int tmp;

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

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

    memset(d, 0, sizeof(int)*(V+1));

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

    return d[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;
}