地址：

题意：分硬币，有1，5，10，25四种硬币，给定每种硬币的数量，给定要组合成的价值，问刚好达到价值时用的硬币最多的情况。

mark：多重背包！本题给出两种方法，特别注意下面一个方法！！！

代码：

需要回溯，于是就加一个path[]存放父亲，dp[]代表个数。由于该题有5，10这两个硬币，多重背包二进制优化的时候可能出现5*2，然后本题要区分开来，所以记录一下就行。

#include 
     
      #include 
      
       #include 
       
        const int N = 10010;int vmax, v[5] = {
   1, 5, 10, 25};int num[30], dp[N], path[N];int max(int a, int b) {
   return a > b ? a : b;}void zero(int p, int k)   //01背包 {    for(int j = vmax; j >= k*v[p]; j--)    {        if(dp[j-k*v[p]]+k > dp[j])        {            dp[j] = dp[j-k*v[p]]+k;            path[j] = p*N+(j-k*v[p]);        }    }}void com(int p)   //完全背包 {    for(int j = v[p]; j <= vmax; j++)    {        if(dp[j-v[p]]+1 > dp[j])        {            dp[j] = dp[j-v[p]]+1;            path[j] = p*N+(j-v[p]);        }    }}void mut()    //多重背包 {    for(int p = 0; p < 4; p++)    {        if(num[p] == 0) continue;        if(v[p] > vmax) return ;        int amount = num[p];        if(v[p]*amount >= vmax) com(p);        else        {            for(int j = 1; j <= amount; j*= 2)            {                zero(p, j);                amount -= j;            }            if(amount) zero(p, amount);        }    }}int main(){    while(scanf("%d", &vmax))    {        for(int j = 0; j < 4; j++)            scanf("%d", num+j);        if(!vmax) break;        for(int k = 1; k <= vmax; k++)            dp[k] = -N;        dp[0] = 0;        path[0] = -1;        mut();        if(dp[vmax] <= 0)        {            puts("Charlie cannot buy coffee.");            continue;        }        memset(num, 0, sizeof(num));        while(vmax)        {            int s1 = path[vmax]/N;            int s2 = path[vmax]%N;            num[v[s1]] += (vmax-s2)/v[s1];            vmax = s2;        }        printf("Throw in %d cents, %d nickels, %d dimes, and %d quarters.\n", num[1], num[5], num[10], num[25]);    }    return 0;}
       
      
     

学习大牛的思路，本题还可以应用完全背包的思路，只不过要多加一个数组used[]存放已经用了多少个同种类的硬币，不能超过给定数量。

注意：这一类题目可以按照一下分析来解决问题，效率是O(NV)的，比二进制优化快！

因为本题是要求硬币尽可能多，所以在更新节点的时候同样的价值大的硬币肯定能不用则不用，只要用了肯定是当前最优的情况，所以可以用used数据记录用过的硬币。但是如果一旦题目变成了硬币尽可能少，那么这种方法就错了，因为价值相同的时候 ，肯定大硬币用的多，数量就少，这就会导致一个问题，就是往后扫描的时候，可能出现大硬币已经用完了，本来这个价值是可以达到的，但是因为这个方法而导致这个价值达不到。那转换个方向，我们可以从硬币最大的开始更新嘛~

#include 
     
      #include 
      
       #include 
       
        const int N = 100010;int v[5] = {
   1, 5, 10, 25};int p,num[30];int dp[N],used[N],path[N];int main(){    int i,j,k;    while(scanf("%d", &p))    {        for(i = 0; i < 4; i++)            scanf("%d", num+i);        if(!p) break;        memset(dp, -1, sizeof(dp));        dp[0] = 0;                for(i = 0; i < 4; i++)        {            memset(used, 0, sizeof(used));            for(j = v[i]; j <= p; j++)            {                if(dp[j-v[i]]+1 > dp[j] && dp[j-v[i]] != -1 && used[j-v[i]] < num[i])                {                    dp[j] = dp[j-v[i]]+1;                    used[j] = used[j-v[i]]+1;                    path[j] = j-v[i];                }            }        }                if(dp[p] == -1) {puts("Charlie cannot buy coffee."); continue;}        memset(num, 0, sizeof(num));        while(dp[p])        {            num[p-path[p]]++;            p = path[p];        }        printf("Throw in %d cents, %d nickels, %d dimes, and %d quarters.\n", num[1], num[5], num[10], num[25]);    }    return 0;}