零崎的朋友很多Ⅰ

时间限制: 2000 ms 内存限制: 65536 kb

 

 

题目描述

零崎有很多朋友，其中有一个叫做lfj的接盘侠。

lfj是一个手残，他和零崎一起玩网游的时候不好好打本，天天看拍卖行，没过多久，就成为了一个出色的商人。时间一长，虽然挣了不少钱，却没时间练级了。

作为lfj的友人，零崎实在看不下去，于是他决定帮lfj一把。当然了，零崎肯定不会自己动手，活还得你们来干。

lfj可以提供给你们拍卖行所有能买到物品的价格和利润，由于游戏产出不限，所以可以假定只要有钱，即使是同一种东西，多少个也都能买到手。lfj还会告诉你他初始的成本。虽然零崎想让你们给出一次交易中利润最大的购买方案，但是lfj觉得只要知道最大利润就可以了。

输入

每组数据第一行为两个整数P和N，表示本金和拍卖行物品种类数。

接下来N行，每行两个数据pi,ci代表第i类物品的利润和购买价格。

1<=P<=20000,1<=N<=300,1<=c,p<=200

输出

对于每组数据，输出一行，为能获得的最大利润

输入样例

3 12 12 31 11 22 1

输出样例

64

Hint

使用if直接比较不要调用max（）以防超时

 

1.分析：

完全背包

我们可以将完全背包转化为01背包求解，我们可以把 一个物品拆分成k个物品(w[x]*k<=C)，然后按照01背包求解即可；

2.实现这种思路的方法：

只需在01背包的基础上修改一点即可，即第二层循环改为正序。

 

for(int j=w[i];j<=c;++j) 解释：在01背包中，我们采用倒序的原因是为了，在决策第i个物品的阶段时，之前dp数组内保存的第i-1个阶段的状态不被破坏。而在完全背包问题中，由于物品有无数件， 更新状态时，我们基于的状态就可以是当前考虑第i个物品的状态了(只不过背包容量不同)。 另外，dp[i]的含义理解为背包容量（不要理解为剩余容量）为j时，考虑前i个物品放入背包，所能得到的最大收益。

1 #include 
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 using namespace std; 6 typedef long long LL; 7 const int maxv=20007; //背包空间上限 8 const int maxk=307;//物品数上限 9 const int negainf=-999999;10 int v[maxk],w[maxk];//w为重量，v为价值11 LL dp[maxv];12 int c,n;//背包空间和物品数13 void init_nofull(){     //题目未要求背包必须装满的初始化方法14     memset(dp,0,sizeof(dp));15     for(int i=0;i<=c;++i){16         dp[c]=0;17     }18 }1926 void start_dp(){27     for(int i=0;i
         
          =0){42             printf("%d\n",dp[c]);43         }44         else{45             //printf("no anwser\n");46         }47     }48 }