Hdoj 5410 CRB and His Birthday【背包变形】

╰半夏微凉° 2022-08-04 12:35 9阅读 0赞

### 题意 ###

> 现在有 m 块钱以及 n 种物品，然后每种物品价格 val，买 x 个送糖果 x \* w1 + w2，问怎么买是的送的糖果最多？

--------------------

### 分析 ###

> 一看就是很明显的背包，问题在于这个w2，我们知道普通的背包放进去的物体得到的价值只和放进去的数量成正比。这里不是正比，假如放了为正比+w2，所以这里还与放与不放有关系。
> 
> **千万不要陷入放于不放中**，其实我们可以对w2这里做一次0-1背包，价值为w1+w2.然后对剩下的进行多重背包或完全背包。
> 
> 因为没有限制数量，所以可以直接完全背包，这样很快，当然可以对剩下的做多重也对，但是切记直接做多重，然后二进制优化中第一个0-1，这样是错的，自己模拟下这组数据  
> 100 2  
> 10 2 1  
> 10 1 2

--------------------

### 代码 ###

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <string>
    #include <algorithm>
    
    using namespace std;
    
    const int N = 2010;
    const int M = 1010;
    
    int capacity[M],w1[M],w2[M];
    int dp[N];
    void Zero_one(int cost,int w,int m)
    {
        for(int i=m;i>=cost;--i)
            dp[i] = max(dp[i],dp[i-cost]+w);
    }
    int main()
    {
    //    freopen("Input.txt","r",stdin);
        int T;
        scanf("%d",&T);
        while(T--)
        {
            int m,n;
            scanf("%d%d",&m,&n);
            for(int i=0;i<n;i++)
                scanf("%d%d%d",&capacity[i],&w1[i],&w2[i]);
            memset(dp,0,sizeof(dp));
            for(int i=0;i<n;i++)
            {
                Zero_one(capacity[i], w1[i]+w2[i], m);
                int k=1;
                int num = m/capacity[i]-1;
                while(k<num)
                {
                    Zero_one(k*capacity[i], k*w1[i], m);
                    num-=k; //
                    k*=2;
                }
                Zero_one(num*capacity[i], num*w1[i], m);
            }
            printf("%d\n",dp[m]);
        }
    
        return 0;
    }