HDU 5410 CRB and His Birthday(01+完全）

灰太狼 2022-06-17 22:12 129阅读 0赞

CRB and His Birthday

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)  
Total Submission(s): 1956 Accepted Submission(s): 923

Problem Description  
Today is CRB’s birthday. His mom decided to buy many presents for her lovely son.  
She went to the nearest shop with M Won(currency unit).  
At the shop, there are N kinds of presents.  
It costs Wi Won to buy one present of i-th kind. (So it costs k × Wi Won to buy k of them.)  
But as the counter of the shop is her friend, the counter will give Ai × x + Bi candies if she buys x(x>0) presents of i-th kind.  
She wants to receive maximum candies. Your task is to help her.  
1 ≤ T ≤ 20  
1 ≤ M ≤ 2000  
1 ≤ N ≤ 1000  
0 ≤ Ai, Bi ≤ 2000  
1 ≤ Wi ≤ 2000

Input  
There are multiple test cases. The first line of input contains an integer T, indicating the number of test cases. For each test case:  
The first line contains two integers M and N.  
Then N lines follow, i-th line contains three space separated integers Wi, Ai and Bi.

Output  
For each test case, output the maximum candies she can gain.

Sample Input  
1  
100 2  
10 2 1  
20 1 1

Sample Output  
21  
Hint  
CRB’s mom buys 10 presents of first kind, and receives 2 × 10 + 1 = 21 candies.

Author  
KUT（DPRK）

Source  
2015 Multi-University Training Contest 10

Recommend  
wange2014

> 题意：  
> CRB生日，妈妈要给他买礼物，妈妈有M元钱，这家店有N种礼物，因为店长和妈妈是熟人，所以若第i种礼物买x件的话，店长会给妈妈Ai\*x+Bi颗糖果，现给出每种礼物的单价、Ai值与Bi值，问妈妈最多能拿到多少颗糖果。
> 
> **题解：**  
> *如果要求得的关系是单纯的线性关系即y=a\*x这种，则可直接当作完全背包来考虑；如果要求得的关 系包含一定的常数即y=a\*x+b这种，则要将该种物品分为两种物品来解决，一种是特殊物品价值为a+b，因为其只有一件所以此种当作01背包来处理；另一种是普通物品价值为a，因为其有无数件所以此种当作完全背包来处理.*

## 代码： ##

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <cmath>
    
    using namespace std;
    
    const int maxn = 2000+10;
    int dp[maxn];
    
    int main()
    {
        int t;
        cin>>t;
        while(t--)
        {
            memset(dp,0,sizeof(dp));
            int m,n;
            cin>>m>>n;
            int w,a,b;
            for(int i=0;i<n;i++)
            {
                cin>>w>>a>>b;
                for(int j=m;j>=w;j--)///01
                    dp[j] = max(dp[j],dp[j-w]+a+b);
                for(int j=w;j<=m;j++)///完全
                    dp[j] = max(dp[j],dp[j-w]+a);
            }
            cout<<dp[m]<<endl;
        }
        return 0;
    }