本文主要是介绍hihocoder 1364 : 奖券兑换（多重背包），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
#1364 : 奖券兑换
时间限制: 20000ms
单点时限: 1000ms
内存限制: 256MB
-
3 10 2 3 8 8 10 10
样例输出 -
11
描述
小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。
输出
一行一个整数，表示最大的价值。
多重背包模型 由于奖品数量N较大 需要将具有同一兑换奖券数量和得到价值的奖品进行归类
得到同一类商品的数量 然后直接使用多重背包
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string.h>
#include <string>
#include <vector>
#include <queue>#define MEM(a,x) memset(a,x,sizeof a)
#define eps 1e-8
#define MOD 10009
#define MAXN 100010
#define MAXM 100010
#define INF 99999999
#define ll __int64
#define bug cout<<"here"<<endl
#define fread freopen("ceshi.txt","r",stdin)
#define fwrite freopen("out.txt","w",stdout)using namespace std;int dp[MAXN];
int n,m;
int card[20][20];
struct node
{int wei,cost,num;
}no[110];void ZeroOnePack(int cost,int wei)
{for(int i=m;i>=cost;i--)dp[i]=max(dp[i],dp[i-cost]+wei);
}void ComPack(int cost,int wei)
{for(int i=cost;i<=m;i++)dp[i]=max(dp[i],dp[i-cost]+wei);
}void MultiPack(int cost,int wei,int amount)
{
// cout<<"n "<<n<<endl;if(cost*amount>=m) ComPack(cost,wei);else{int k=1;while(k<amount){ZeroOnePack(k*cost,k*wei);amount-=k;k<<=1;}ZeroOnePack(amount*cost,amount*wei);}
}int main()
{
// fread;while(scanf("%d%d",&n,&m)!=EOF){MEM(card,0);for(int i=0;i<n;i++){int w,p;scanf("%d%d",&w,&p);card[w][p]++;}n=0;for(int i=0;i<110;i++)no[i].num=0;for(int i=0;i<11;i++)for(int j=0;j<11;j++){if(card[i][j]){no[n].wei=j;no[n].cost=i;no[n].num=card[i][j];n++;}}
// cout<<"n "<<n<<endl;MEM(dp,0);for(int i=0;i<n;i++){
// printf("%d %d %d\n",no[i].cost,no[i].wei,no[i].num);MultiPack(no[i].cost,no[i].wei,no[i].num);}printf("%d\n",dp[m]);}return 0;
}
这篇关于hihocoder 1364 : 奖券兑换（多重背包）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
