POJ 1787 Charlie's Change

多重背包 可行性+路径记录

题意是说你要用很多其它的零钱去买咖啡。最后输出你分别要用的 1，5 ，10 。25 的钱的数量。

多重背包二进制分解。然后记录下 这个状态。最后逆向推就可以。

#include<cstdio>

#include<cstring>

#include<string>

#include<queue>

#include<algorithm>

#include<map>

#include<stack>

#include<iostream>

#include<list>

#include<set>

#include<cmath>

#define INF 0x7fffffff

#define eps 1e-6

#define LL long long

using namespace std;

int dp[10001];

int cot[4];

int value[]={1,5,10,25};

int n;

struct lx

{

    int va,co;

}v[10001];

int zero(int cost,int i,int co)

{

    cost*=co;

    for(int j=n;j>=cost;j--)

        if(dp[j-cost]+co>dp[j])

        {

            dp[j]=dp[j-cost]+co;

            v[j].va=i;

            v[j].co=co;

        }

}

int main()

{

    while(scanf("%d",&n))

    {

        for(int i=0;i<4;i++)

            scanf("%d",&cot[i]);

        if(n==0)return 0;

        for(int i=0;i<=n;i++)

            dp[i]=-100001;

        dp[0]=0;

        for(int i=0;i<4;i++)

        {

            if(cot[i]==0)continue;

            if(value[i]*cot[i]>=n)

            {

                for(int j=value[i];j<=n;j++)

                    if(dp[j-value[i]]+1>dp[j])

                    {

                        dp[j]=dp[j-value[i]]+1;

                        v[j].va=i;

                        v[j].co=1;

                    }

            }

            else

            {

                int k=1;

                int tmp=cot[i];

                while(k<tmp)

                {

                    zero(value[i],i,k);

                    tmp-=k;

                    k*=2;

                }

                zero(value[i],i,tmp);

            }

        }

        if(dp[n]<=0)puts("Charlie cannot buy coffee.");

        else

        {

//            for(int i=0;i<=n;i++)

//                printf("%d :  %d*%d\n",i,v[i].co,v[i].va);

            memset(cot,0,sizeof(cot));

            while(n)

            {

                int i=v[n].va;

                int co=v[n].co;

                cot[i]+=co;

//                printf("%d ==\n",co);

                n-=value[i]*co;

            }

            printf("Throw in %d cents, %d nickels, %d dimes, and %d quarters.\n",cot[0],cot[1],cot[2],cot[3]);

        }

    }

}