POJ 1276 Cash Machine

题意：给你一个给定的现金数量goal，还有你拥有的n种面值的现金。

接下来就是n种面值的现金你各拥有多少张。要你求出不超过给定goal的能用你手上拥有现金凑成的最大值！

思路：多重背包问题，状态方程dp(i,v)=max(dp(i,j),dp(i-1,v-kci)+kwi);

优化后AC代码：

#include<stdio.h>
#include<string.h>
struct p
{
    int n;
    int d;
}num[11];
int dp[100010];

int main()
{
    int i,j,n,goal,k,cmax;
    while(scanf("%d%d",&goal,&n)!= EOF)
    {
        for(i=0;i<n;i++)
            scanf("%d%d",&num[i].n,&num[i].d);
        memset(dp,0,sizeof(dp));
        dp[0]=1;       //c从0开始
        cmax=0;
        for(i=0;i<n;i++)
            for(j=cmax;j>=0;j--)
                if(dp[j])   //如果出现过
                for(k=1;k<=num[i].n;k++)
                {
                    int temp=j+k*num[i].d;
                    if(temp>goal)
                        break;
                    dp[temp]=1;     //从当前位置开始标记，一直向下搜
                    if(temp>cmax)
                        cmax=temp;
                }
        printf("%d\n",cmax);
    }
    return 0;
}

POJ 1276 Cash Machine,布布扣,bubuko.com

POJ 1276 Cash Machine

原文：http://blog.csdn.net/u012313382/article/details/38017621