HDOJ(HDU).2191. 悼念512汶川大地震遇难同胞――珍惜现在，感恩生活 (DP 多重背包+二进制优化)

时间：2021-05-23 23:50:20

HDOJ(HDU).2191. 悼念512汶川大地震遇难同胞――珍惜现在，感恩生活 (DP 多重背包+二进制优化)

题意分析

首先C表示测试数据的组数，然后给出经费的金额和大米的种类。接着是每袋大米的价格，重量和袋数。

每种大米的数量是有限的，应该能看出是多重背包的问题。关键是多重背包的处理方法。对多重背包采用二进制优化的方法。设同种大米的数量为n,每袋的价格为v，那么把同一种大米分别拆成1,2,4,8,16……(直到不够2^n时，剩下的单独分成一组)，拆分的价格也分别对应是v,2v,4v,8v,16v。按照这样的方式把所有的大米的拆分好，然后依次放置在同一个数组里面，对这些拆分好的大米，做01背包即可。

代码总览

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#define nmax 105

#define INIT(x,y) memset(x,y,sizeof(x))

using namespace std;

int dp[nmax*nmax];

int price[nmax*nmax],weight[nmax*nmax];

int main()

{

 //freopen("in.txt","r",stdin);

    int C;

    scanf("%d",&C);

    while(C--){

        INIT(dp,0);

        INIT(price,0);

        INIT(weight,0);

        int n,m;

        int cnt = 1;

        scanf("%d%d",&m,&n);

        for(int i =1 ;i<= n;++i){

            int pri,wei,num;

            scanf("%d%d%d",&pri,&wei,&num);

            //二进制优化

            for(int j = 1;j<=num; j*=2){

                price[cnt] = j*pri;

                weight[cnt++] = j*wei;

                num-=j;

            }

            if(num>0){

                price[cnt] = num*pri;

                weight[cnt++] = num*wei;

            }

        }

        //转换成01背包

        for(int k = 0; k<=cnt;++k){

            for(int j =m;j>=price[k];j-- )

                dp[j] = max(dp[j],dp[j-price[k]]+weight[k]);

        }

        printf("%d\n",dp[m]);

    }

    return 0;

}

相关文章