#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 : 奖券兑换(二进制背包)