Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
背包九讲之完全背包,恰好装满,二维数组
/*
* 背包九讲之完全背包 恰好装满 二维数组
* 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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.