HDU2191 悼念512汶川大地震遇难同胞（多重背包）

题目链接。

分析：

一直在看多重背包，一开始做了几个，几乎全部TLE。原来是要用二进制优化，学习了一下（详情见本博客）。

第一种做法：

#include <stdio.h>
#include <string.h>

#define MAXN 3000

int n, m;

int value[MAXN], weight[MAXN];
int dp[150];

int max(int x, int y){
    return x > y ? x : y;
}

int main(){
    int T, p, h, c, cnt, i, j;
    scanf("%d", &T);
    while(T--){
        memset(dp, 0, sizeof(dp));
        scanf("%d %d", &n, &m);
        cnt = 0;
        while(m--){
            scanf("%d %d %d", &p, &h, &c);
            for(i=1; i<=c; i<<=1){
                value[cnt] = p*i;
                weight[cnt++] = h*i;
                c -= i;
            }

            if(c > 0){
                value[cnt] = p*c;
                weight[cnt++] = h*c;
            }
        }
        for(i=0; i<cnt; i++){
            for(j=n; j>=value[i]; j--){
                dp[j] = max(dp[j], dp[j-value[i]]+weight[i]);
            }
        }
        printf("%d\n", dp[n]);
    }

    return 0;
}

第二种做法：

0/1背包和完全背包结合。

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int dp[120];

int main(){
    int T, n, m, p, w, c, i, k;

    scanf("%d", &T);
    while(T--){
        memset(dp, 0, sizeof(dp));
        scanf("%d %d", &n, &m);
        while(m--){
            scanf("%d %d %d", &p, &w, &c);
            if(p*c >= n){
                for(i=p; i<=n; i++){
                    if(dp[i] < dp[i-p]+w) dp[i] = dp[i-p]+w;
                }
            }
            else{
                k = 1;
                while(c){
                    if(k > c) k = c;
                    c -= k;
                    for(i=n; i>=k*p; i--){
                        if(dp[i] < dp[i-k*p]+k*w) dp[i] = dp[i-k*p]+k*w;
                    }
                    k <<= 1;
                }
            }
        }
        printf("%d\n", dp[n]);
    }
    return 0;
}

后来用了下贪心，没对。查了下，说的有理。