#1364 : 奖券兑换(二进制背包)

2018年03月26日 11点热度 0人点赞 0条评论

#1364 : 奖券兑换

时间限制:20000ms
单点时限:1000ms
内存限制:256MB

描述

小Hi在游乐园中获得了M张奖券,这些奖券可以用来兑换奖品。

可供兑换的奖品一共有N件。第i件奖品需要Wi张奖券才能兑换到,其价值是Pi。  

小Hi使用不超过M张奖券所能兑换到的最大奖品总价值是多少?

输入

第一行两个整数N,M。  

接下来N行,每行两个整数Wi,Pi。  

对于 50%的数据: 1≤N,M≤1000  

对于 100%的数据: 1≤N,M≤105,1≤Pi,Wi≤10。  

输出

一行一个整数,表示最大的价值。

样例输入

3 10  
2 3  
8 8   
10 10

样例输出

11

//易错点:从2的0次方开始的,不是从2的1次方开始
#include
#include
using namespace std;
const int mn=1e5+100;
int n,m,dp[mn],num[12][12];
int main() {
	cin>>n>>m;
	for(int i=0; i=t) {
				xx=x*t;
				yy=y*t;
				for(int j=m; j>=xx; --j)
					dp[j]=max(dp[j],dp[j-xx]+yy);
				num[x][y]-=t;
				t<<=1;
			}
			if(num[x][y]) {
				xx=x*num[x][y];
				yy=y*num[x][y];
				for(int j=m; j>=xx; --j)
					dp[j]=max(dp[j],dp[j-xx]+yy);
			}
		}
	cout<

未经允许不得转载!#1364 : 奖券兑换(二进制背包)

update

纸上得来终觉浅, 绝知此事须躬行。