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