HDU 2191 悼念512【多重背包+二进制优化】

大意分析：

多重背包，转化为01背包即可

可以用二进制进行优化

代码：（代码没有优化，下题是优化才可过的）

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 using namespace std;
 5 
 6 const int maxn = 105;
 7 
 8 int n, m, tot;
 9 int p[2005], h[2005];
10 int dp[maxn];
11 int solve() {
12     memset(dp, 0, sizeof(dp));
13     for(int i = 1; i < tot; i++) {
14         for(int j = n; j >= p[i]; j--) {
15             dp[j] = max(dp[j], dp[j - p[i]] + h[i]);
16         }
17     }
18     return dp[n];
19 }
20 
21 int main() {
22     int t;
23     int a, b, c;
24     scanf("%d",&t);
25     while(t--) {
26         tot = 1;
27         scanf("%d %d",&n, &m);
28         while(m--) {
29             scanf("%d %d %d",&a, &b, &c);
30             while(c--) {
31                 p[tot] = a; h[tot++] = b;
32             }
33         }
34         printf("%d
",solve());
35     }
36     return 0;
37 }

View Code