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=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;
}
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.