poj1276(Cash Machine + 多重背包)

题目链接：http://poj.org/problem?id=1276

题意：一提款机里存有N种面值的钱币，有n1张面值d1的纸币，n2张面值d2的纸币......nN张面值dN的钱币，现在有一顾客，要提取现在数量cash，问提款机利用这些纸币最多能为顾客提供多少现金。（呵呵，纸币只能一张一张的，不能半张就算d/2的现金啊，提款机也吐不出来，娱乐娱乐！！！）

赤裸的多重背包，直接套模版，学习背包的同学，可以参照我这个（当然要先看下背包九讲：http://love-oriented.com/pack/，先了解了解），我是绝对套得背包九讲里面多重背包的模版滴！！！

代码：

#include<stdio.h>#include<string.h>#define MAXN 1005#define MAXM 100005int amount[MAXN],value[MAXN];int dp[MAXM];int n,cash;int max(int a,int b){return a>b ? a : b;}void CompletePack(int cost)//完全背包{    for(int v=cost;v<=cash;v++){dp[v]=max(dp[v],dp[v-cost]+cost);}}void OneZeroPack(int cost)//01背包{for(int v=cash;v>=cost;v--){dp[v]=max(dp[v],dp[v-cost]+cost);}}void MultiplePack(int id)//多重背包{   if(value[id]*amount[id] > cash)   {        CompletePack(value[id]);return ;   }   int k=1;   while(k<amount[id])   {   OneZeroPack(k*value[id]);   amount[id] -= k;   k *= 2;   }   OneZeroPack(amount[id]*value[id]);}int main(){int i;int ans;    while(scanf("%d%d",&cash,&n)!=EOF){for(i=0;i<n;i++)scanf("%d%d",&amount[i],&value[i]);memset(dp,0,sizeof(dp));for(i=0;i<n;i++)MultiplePack(i);ans = 0;for(i=0;i<=cash;i++)if(dp[i]>ans)ans = dp[i];printf("%d\n",ans);}return 0;}