01背包+完全背包 HDU - 5410 

喜欢ヅ旅行 2022-06-17 09:27 142阅读 0赞

Today is CRB's birthday. His mom decided to buy many presents for her lovely son.  
She went to the nearest shop with M  
M  
Won(currency unit).  
At the shop, there are N  
N  
kinds of presents.  
It costs Wi  
Wi  
Won to buy one present of i  
i  
\-th kind. (So it costs k  
k  
× Wi  
Wi  
Won to buy k  
k  
of them.)  
But as the counter of the shop is her friend, the counter will give Ai × x + Bi  
Ai × x + Bi  
candies if she buys x  
x  
(x  
x  
>0) presents of i  
i  
\-th kind.  
She wants to receive maximum candies. Your task is to help her.  
1 ≤ T  
T  
≤ 20  
1 ≤ M  
M  
≤ 2000  
1 ≤ N  
N  
≤ 1000  
0 ≤ Ai, Bi  
Ai, Bi  
≤ 2000  
1 ≤ Wi  
Wi  
≤ 2000  
  
Input  
  
There are multiple test cases. The first line of input contains an integer T  
T  
, indicating the number of test cases. For each test case:  
The first line contains two integers M  
M  
and N  
N  
.  
Then N  
N  
lines follow, i  
i  
\-th line contains three space separated integers Wi  
Wi  
, Ai  
Ai  
and Bi  
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.

#include <iostream>
    #include <cstring>
    #include <cstdio>
    #include <string>
    #include <map>
    #include <queue>
    #include <set>
    #include <algorithm>
    #define LL long long
    #define MAX 2005
    using namespace std;
    int dp[MAX];
    int w[MAX],a[MAX],b[MAX];
    int t,m,n;
    int main()
    {
        scanf("%d",&t);
        while(t--)
        {
            scanf("%d%d",&m,&n);
            for(int i=1;i<=n;i++)
                scanf("%d%d%d",&w[i],&a[i],&b[i]);
            memset(dp,0,sizeof(dp));
            for(int i=1;i<=n;i++)
                for(int j=m;j>=w[i];j--)
            {
                dp[j]=max(dp[j],dp[j-w[i]]+a[i]+b[i]);   //先通过01背包来确定拿不拿这件商品的最大价值
            }
            for(int i=1;i<=n;i++)
                for(int j=w[i];j<=m;j++)
            {
                dp[j]=max(dp[j],dp[j-w[i]]+a[i]);  //用完全背包计算拿了x件商品的最大价值（a[i]*x+b[i])
            }
            printf("%d\n",dp[m]);
        }
    
    
        return 0;
    }
    
    /*题意：
    有M多的钱 去买n种商品
    每种商品的价格为w  如果你买x个这种商品 你会得到 a*x+b个糖果
    问最多能得到多少糖果*/
    
    /*思路：
    对于每件商品 你如果买一件 那么你会得到a+b个糖果
    如果再次基础上每一次的购买你就只能得到a个糖果
    所以可以看所这种商品有两种价值
    第一种价值只有一次 用01背包解决
    第二种价值可以无限次购买 用完全背包解决 */