hdu 5410 CRB and His Birthday(混合背包)

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
 

题意:你有M块钱,现在有N件商品

第i件商品要Wi块,如果你购买x个这样的商品,你将得到Ai*x+Bi个糖果

问能得到的最多的糖果数

 

思路:非常好的一道01背包和完全背包结合的题目

首先,对于第i件商品,如果只买1个,得到的价值是Ai+Bi

如果在买1个的基础上再买,得到的价值就是Ai

也就是说,除了第一次是Ai+Bi,以后购买都是Ai

那么,我们能否将i商品拆分成两种商品,其中两种商品的代价都是Wi,

第一种的价值是Ai+Bi,但是只允许买一次

第二种的价值是Ai,可以无限次购买

 

接下来我们来讨论这样拆的正确性

理论上来讲,买第二种之前,必须要买第一种

但是对于这道题,由于Ai+Bi>=Ai是必然的,因为Bi肯定是非负

所以对于代价相同,价值大的肯定会被先考虑

换句话来说,如果已经开始考虑第二种商品了,那么第一种商品就肯定已经被添加到背包里了~

 

所以,这题我们把n件商品拆分成2*n件商品,对于第一种商品做01背包,对于第二种商品做完全背包,这样就把题目转换成了非常熟悉的题目,也就能顺利AC了

 
 #include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define N 1006
int v,n;
int w[N<<],a[N<<],b[N<<];
int dp[N<<];
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&v,&n);
for(int i=;i<=n;i++)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
w[i]=x,a[i]=y+z;
w[i+n]=x,a[i+n]=y;
}
memset(dp,,sizeof(dp)); for(int i=;i<=n;i++)
{
for(int j=v;j>=w[i];j--)
{
dp[j]=max(dp[j],dp[j-w[i]]+a[i]);
}
} for(int i=n+;i<=*n;i++)
{
for(int j=w[i];j<=v;j++)
{
dp[j]=max(dp[j],dp[j-w[i]]+a[i]);
}
} printf("%d\n",dp[v]); }
return ;
}
上一篇:TI(德州仪器) TMS320C674x逆向分析之一


下一篇:一文了解安卓APP逆向分析与保护机制