咖啡硬币问题题解

题目分析

本题要求用给定数量的四种硬币（1美分、5美分、10美分、25美分）恰好支付咖啡价格P，并使硬币数量最多。这是一个典型的多重背包问题，但目标是最大化物品数量而非价值。

算法思路

使用动态规划解决该问题，核心思路如下：

1. 状态定义：

   • dp[j]：凑出金额j所需的最大硬币数量
   • num[j]：凑出金额j时当前硬币的使用数量
   • path[j]：记录状态转移路径，用于回溯硬币组合

2. 状态转移：

   • 对于每种硬币面值c[i]（i=1~4），遍历金额j从c[i]到P
   • 若使用当前硬币能使dp[j]更大且不超过该硬币的可用数量，则更新状态

3. 初始化：

   • dp[0] = 1，表示金额0可以被凑出（使用0个硬币）
   • 其余dp值初始化为0，表示无法凑出

4. 遍历顺序：

   • 外层按硬币面值从小到大遍历
   • 内层按金额从小到大遍历（完全背包的遍历顺序）

5. 结果判断：

   • 若dp[P] > 0，说明可以凑出金额P，通过path数组回溯每种硬币的使用数量
   • 否则输出无法凑出的信息

代码实现分析

#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
int dp[10010],ans[10010],num[10010],path[10010];
int p,c[5]={0,1,5,10,25},t[5];
int main()
{
    while(scanf("%d %d %d %d %d",&p,&t[1],&t[2],&t[3],&t[4])>0&&(p+t[1]+t[2]+t[3]+t[4]))
    {
        memset(dp,0,sizeof(dp));
        memset(ans,0,sizeof(ans));
        memset(path,0,sizeof(path));
        dp[0]=1;
        for(int i=1;i<=4;i++)
        {
            memset(num,0,sizeof(num));
            for(int j=c[i];j<=p;j++)
            if(dp[j-c[i]]&&dp[j-c[i]]+1>dp[j]&&num[j-c[i]]<t[i])   // 关键条件判断
            {
                dp[j]=dp[j-c[i]]+1;
                num[j]=num[j-c[i]]+1;
                path[j]=j-c[i];
            }
        }
        int i=p;
        if(dp[p]>0)
        {
            while(i!=0)
            {
                ans[i-path[i]]++;
                i=path[i];
            }
            printf("Throw in %d cents, %d nickels, %d dimes, and %d quarters.\n",ans[1],ans[5],ans[10],ans[25]);
        }
        else  printf("Charlie cannot buy coffee.\n");
    }
    return 0;
}

关键代码解释

1. 状态转移条件：

   if(dp[j-c[i]] && dp[j-c[i]]+1 > dp[j] && num[j-c[i]] < t[i])
   

   • dp[j-c[i]]：确保金额j-c[i]可以被凑出
   • dp[j-c[i]]+1 > dp[j]：使用当前硬币能使硬币数量更多
   • num[j-c[i]] < t[i]：当前硬币的使用数量未超过可用数量

2. 路径记录：

   • path[j] = j-c[i]：记录从j-c[i]转移到j，用于后续回溯

3. 回溯过程：

   while(i!=0)
   {
       ans[i-path[i]]++;
       i=path[i];
   }
   

   • 通过path数组回溯，统计每种硬币的使用次数

复杂度分析

• 时间复杂度：O(4 * P) = O(P)，其中P为咖啡价格
• 空间复杂度：O(P)，主要用于存储dp数组和辅助数组

该算法通过动态规划高效解决了多重背包问题，确保在满足金额约束的前提下使用最多的硬币。