题意：

有1，5，10，25四种硬币，给每种硬币的数量和要组合成的价值，求刚好达到价值时用的硬币最多，然后还要输出具体的用的数量

前言：

一开始是偶然看见了kuangbin爷的题解说是完全背包+路径，很好奇啊。

思路(kuangbin爷代码 Orz)：

一个完全背包，加个计数，加个路径。

因为题目要求是求一个max硬币数量，所以直观上我们感觉就是面值小的硬币用的越多越好，然后在dp更新的时候，基于小面值使用大面值。所以val数组是从小到大，目的是尽可能使用更多的小面值硬币达到dp数组是每次都是最多的。然而如果是求最小硬币数，直接就可以把面值数组掉一下头就好啦~

突然有个问题(太弱就会瞎想)：

有没有存在可能被给出的P面值没有被更新到，虽然dp数组判断条件是判断谁大，所以初始化0就好了(P>=1)，一旦符合就是有符合的条件。所以是成立。

忽略以上的问题，利用完全背包的思想：

首先在更新的时候必须保证dp[j-val[i]]>=0的，第一枚硬币的更新是以 j-val[i] = 0为基础开始的，以至于dp数组才可以代表的是 j 面值的最大硬币数。所以初始化dp是负数。

然后加一个cnt，非常nice的一个想法。

具体写法：

①：我们可以开一个num数组去记录某价值下的某硬币的使用情况。

②：我们可以开个pre数组去记录一下某 j 面值的前面的j-val[i]，然后递归到0，中间的差值就是被使用价值的硬币，再开一个数组记录一下就好了。

除了这个方法，还有多重背包+路径；

贴一发挫code……….

#include<cstdio>

#include<iostream>

#include<math.h>

#include<string.h>

#include<algorithm>

using namespace std;

#define eps 1e-8

typedef __int64 LL;

const int N=1e4+10;

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

int dp[N];  //在该面值的最大硬币数量

int num[5];

int pre[N];//记录背包路径

int cnt[N];//每次更新是临时计数

int ans[30]; //计数

int main()

{

    int n;

    int t;

    bool flag=true;

    while(1)

    {

        scanf("%d",&t);

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

        {

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

            if(num[i]) flag=true;

        }

        if(!t&&!num[0]&&!num[1]&&!num[2]&&!num[3]) break;//在这里wa了，以后判0乖乖这样做。

        memset(pre,0,sizeof(pre));

        memset(dp,-1,sizeof(dp));

        dp[0]=0;

        pre[0]=-1;

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

        {

            memset(cnt,0,sizeof(cnt));

            for(int j=val[i];j<=t;j++)

            {

                if(dp[j-val[i]]>=0&&(dp[j-val[i]]+1)>dp[j]&&num[i]>cnt[j-val[i]])//首先dp[j-val[i]]>=0，因为要保证你前面那个是满足的

                {

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

                    cnt[j]=cnt[j-val[i]]+1;

                    pre[j]=j-val[i];

                }

            }

        }

        if(dp[t]<0)

        {

            printf("Charlie cannot buy coffee.\n");

            continue;

        }

        //printf("%d\n",dp[t]);

        memset(ans,0,sizeof(ans));

        int x=t;

        while(1)

        {

            if(pre[x]==-1) break;

            ans[x-pre[x]]++;

            x=pre[x];

        }

        printf("Throw in %d cents, %d nickels, %d dimes, and %d quarters.\n",ans[1],ans[5],ans[10],ans[25]);

    }

    return 0;

}