农夫约翰硬币支付问题解析

这道题目要求我们帮助农夫约翰以最少的硬币数量完成支付。约翰需要支付T美分，他有N种不同面值的硬币，每种硬币有特定的数量。店主则有无限数量的各种硬币。

解题思路

这个问题可以通过动态规划解决：

1. 我们需要同时考虑两个方面：

   • 约翰支付的金额需要大于等于T
   • 店主找零的金额为(支付金额-T)

2. 我们可以使用两个DP数组：

   • dp[i] 表示约翰支付i美分时最少需要的硬币数量（使用多重背包）
   • dp2[i] 表示店主找零i美分时最少需要的硬币数量（使用完全背包）

3. 最终答案是：对于所有可能的支付金额i（i≥T），dp[i] + dp2[i-T] 的最小值

代码解析

下面是完整的C++代码，我将对关键部分进行解释：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define INF 1e9
 
int n;//n种硬币
int m;//购买商品的价值
int up_bound;//DP价值上界
int val[100+5];//每种硬币价值
int num[100+5];//每种硬币数目
int dp[55555]; //多重背包
int dp2[55555];//完全背包
 
//1次01背包
void ZERO_ONE_PACK(int *dp,int cost,int sum)
{
    for(int i=up_bound;i>=cost;i--)
        dp[i] = min(dp[i], dp[i-cost]+sum);//注意这里是+sum
}
 
//1次完全背包
void COMPLETE_PACK(int *dp,int cost)
{
    for(int i=cost;i<=up_bound;i++)
        dp[i] = min(dp[i], dp[i-cost]+1);
}
 
//1次多重背包
void MULTIPLY_PACK(int *dp,int cost,int sum)
{
    if(cost*sum>=up_bound)
    {
        COMPLETE_PACK(dp,cost);
        return ;
    }
 
    int k=1;
    while(k<sum)
    {
        ZERO_ONE_PACK(dp,cost*k,k);
        sum -=k;
        k *=2;
    }
    ZERO_ONE_PACK(dp,cost*sum,sum);
}
 
int main()
{
    while(scanf("%d%d",&n,&m)==2)
    {
        //读取输入+计算上界
        int max_val=0;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&val[i]);
            max_val= max(max_val,val[i]);
        }
        for(int i=1;i<=n;i++)
            scanf("%d",&num[i]);
        up_bound=max_val*max_val+m;//上界
 
        //初始化dp和dp2
        for(int i=1;i<=up_bound;i++)
            dp[i]=dp2[i]=INF;
        dp[0]=dp2[0]=0;
 
        //递推过程
        for(int i=1;i<=n;i++)
        {
            MULTIPLY_PACK(dp,val[i],num[i]);
            COMPLETE_PACK(dp2,val[i]);
        }
 
        //统计结果
        int ans=INF;
        for(int i=m;i<=up_bound;i++)
            ans= min(ans, dp[i]+dp2[i-m]);
        printf("%d\n",ans==INF?-1:ans);
    }
    return 0;
}

关键算法解析

1. 上界计算：

   • up_bound = max_val * max_val + m，这是为了确保我们考虑了所有可能的支付金额

2. 背包算法：

   • ZERO_ONE_PACK：处理01背包问题（某种硬币只用一个）
   • COMPLETE_PACK：处理完全背包问题（某种硬币可以用无限个）
   • MULTIPLY_PACK：处理多重背包问题（某种硬币有固定数量）
     • 使用二进制优化将多重背包转化为01背包

3. 动态规划过程：

   • dp[i]：表示约翰支付i美分所需的最少硬币数
   • dp2[i]：表示店主找零i美分所需的最少硬币数
   • 最终答案：min(dp[i] + dp2[i-m])，其中i从m到up_bound

时间复杂度分析

• 读取输入：O(N)
• 计算上界：O(N)
• 动态规划：O(N * up_bound)
• 统计结果：O(up_bound)

总体时间复杂度为O(N * up_bound)，其中up_bound约为max_val² + m。

空间复杂度分析

• 存储硬币信息：O(N)
• 动态规划数组：O(up_bound)

总体空间复杂度为O(up_bound)。

这个算法通过巧妙地结合多重背包和完全背包，解决了农夫约翰的最优支付问题。