【二进制优化-多重背包】zznu-oj-2120 : 安详--如何用尽钱币打赏主播获得最大好感度

2120 : 安详

题目描述

spring最近喜欢上了B站新秀主播，身为顿顿吃黄焖鸡的土豪，当然要过去打赏一番，但是spring还是喜欢精打细算，所以在打赏的时候，想要掏出有限的钱，获得主播的最大好感。

主播的好感值是通过送不同的礼物而提升不同，不同礼物的赠送，可以增加的好感值也是不同的，当然礼物的价格更是不同。

输入

输入第一行为两个整数n,m.分别表示有n种不同礼物（1e2）和总金钱数m（1e6），以下n行每行有三个数字，分别表示该礼物的个数（int）和价格（int）以及好感值（int）。 多实例

输出

求spring拿出的钱可以送出的最大好感值。

样例输入

复制

2 10
4 2 100
2 4 100

样例输出

复制

400

---

多重背包解决思路：

 题目：有N种物品和一个容量为V的背包。第i种物品最多有num[i]件可用，每件容量是c[i]，价值是w[i]。

转换成01背包：二进制优化方法是：将第i种物品分成若干件物品，其中每件物品有一个系数，这件物品的容量和价值均是原来的容量和价值乘以这个系数。使这些系数分别为1,2,4,...,2^(k-1),（以及二进制尾数部分）num[i]-2^k+1，且k是满足num[i]-2^k+1>0的最大整数。例如，如果n[i]为13，就将这种物品分成系数分别为1,2,4,6的四件物品。

　　

#define N 10008
#define M 1000008

ll dp[M];
struct node{
    ll c,w;  //c为cost，w为好感度
}p[N];

int main(){

    ll nn,m;
    while(scanf("%lld%lld",&nn,&m)!=EOF){
        int cnt=0;//拆分后的物品数
        ll t,c,w;

        for(int i=1;i<=nn;i++){
            scanf("%lld%lld%lld",&t,&c,&w);  //数量，花费，好感度
            int x=1;
            while(t-x>0){
                t-=x;
                p[++cnt].c=x*c;
                p[cnt].w  =x*w;
                x*=2;
            }
            p[++cnt].c=t*c; //跑完上面的循环后剩下t
            p[cnt].w=t*w;
        }

        memset(dp,0,sizeof(dp));
        for(int i=1;i<=cnt;i++){
            for(int j=m;j>=p[i].c;j--){  //花费自大到小
                dp[j]=max(dp[j],dp[j-p[i].c]+p[i].w);
            }
        }


        printf("%lld
",dp[m]);
    }

    return 0;
}
#define N 10008
#define M 1000008

ll dp[M];
struct node{
    ll c,w;  //c为cost，w为好感度
}p[N];

int main(){

    ll nn,m;
    while(scanf("%lld%lld",&nn,&m)!=EOF){
        int cnt=0;//拆分后的物品数
        ll t,c,w;

        for(int i=1;i<=nn;i++){
            scanf("%lld%lld%lld",&t,&c,&w);  //数量，花费，好感度
            int x=1;
            while(t-x>0){
                t-=x;
                p[++cnt].c=x*c;
                p[cnt].w  =x*w;
                x*=2;
            }
            p[++cnt].c=t*c; //跑完上面的循环后剩下t
            p[cnt].w=t*w;
        }

        memset(dp,0,sizeof(dp));
        for(int i=1;i<=cnt;i++){
            for(int j=m;j>=p[i].c;j--){  //花费自大到小
                dp[j]=max(dp[j],dp[j-p[i].c]+p[i].w);
            }
        }


        printf("%lld
",dp[m]);
    }

    return 0;
}