POJ 1276 Cash Machine【多重背包DP】

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

多重背包问题，为重量与价值相等的特殊情况，转为01背包

将物品拆成2^k[i]之和，如13=1+2+4+6

时间复杂度：<math>O(V*Σlog n[i])

处理 一件 多重背包中物品的过程，其中amount表示物品的数量：
		
procedure MultiplePack(cost,weight,amount)
    if cost*amount>=V				
        CompletePack(cost,weight)	//单一物件超出最大值则转换成完全背包
        return
    integer k=1
    while k<amount
        ZeroOnePack(k*cost,k*weight)	//01背包
        amount=amount-k
        k=k*2
    ZeroOnePack(amount*cost,amount*weight)	//处理剩余数量，01背包。如4=1+2，处理剩余的1
           

#include<string.h>
#include<stdio.h>
#define max(a,b) ( (a) > (b) ? (a) : (b) )
int dp[100005];
int main()
{
	int cash,n,d,i,j,m,k;
	while(scanf("%d%d",&cash,&m)!=EOF)
	{
		memset(dp,0,sizeof(dp));
		for(i=0;i<m;i++)
		{
			scanf("%d%d",&n,&d);
			if(n*d>cash)
			{	
				for(j=d;j<=cash;j++)
						dp[j] = max ( dp[j],dp[j - d ] +  d );
				continue;
			}
			k=1;
			while(k<n)
			{		
				for(j=cash;j>=k*d;j--)
					dp[j] = max ( dp[j],dp[ j - k * d ] + k* d);
				n-=k;
				k<<=1;
			}
			for(j=cash;j>=n*d;j--)
				dp[j]= max (dp[j],dp[ j - n * d ] + n* d );
		}
		printf("%d\n",dp[cash]);
	}
	return 0;
}