背包九讲之完全背包，恰好装满，二维数组

complete_pack-1.cpp

/*
 * 背包九讲之完全背包 恰好装满 二维数组
 *  from: http://acm.hdu.edu.cn/showproblem.php?pid=1114
 *  reference: https://blog.csdn.net/liujc_/article/details/44003167
 */
#include <bits/stdc++.h>

#define NMAX 500
#define PMAX 1000000001

int P[NMAX], W[NMAX];

using namespace std;

/*
 * d[i][v] = min{ d[i-1][v], d[i][v-c[i]]+w[i] }
 */
int piggy_bank(int P[], int W[], int n, int V) {
    int **d = new int *[n+1];
    int p;

    for (int i = 0; i <= n; i++) {
        d[i] = new int[V+1];
        for (int j = 0; j <= V; j++)
            d[i][j] = PMAX;
    }

    for (int i = 0; i <= n; i++) {
        d[i][0] = 0;
        for (int j = 1; i > 0 && j <= V; j++) {
            if (j >= W[i-1]) {
                p = d[i][j-W[i-1]] + P[i-1];
                d[i][j] = (d[i-1][j] < p) ? d[i-1][j] : p;
            } else
                d[i][j] = d[i-1][j];
        }
    }

    p = d[n][V];

    for (int i = 0; i <= n; i++)
        delete d[i];

    return p;
}

int main() {
    int T, E, F, N, d;

    cin >> T;

    for (int i = 0; i < T; i++) {
        cin >> E >> F; // weight and number

        cin >> N;

        for (int j = 0; j < N; j++)
            cin >> P[j] >> W[j];

        d = piggy_bank(P, W, N, F-E);
        if (d == PMAX)
            cout << "This is impossible." << endl;
        else
            cout << "The minimum amount of money in the piggy-bank is " << d << "." << endl;
    }

    return 0;
}