`
rein07
  • 浏览: 21912 次
  • 性别: Icon_minigender_1
  • 来自: 南京
社区版块
存档分类
最新评论

背包问题之硬币找零问题

 
阅读更多
设有6 种不同面值的硬币,各硬币的面值分别为5 分,1 角,2 角,5 角,1 元,2元。现要用这些面值的硬币来购物和找钱。购物时可以使用的各种面值的硬币个数存于数组Coins[1:6]中,商店里各面值的硬币有足够多。在1次购物中希望使用最少硬币个数。例如,1 次购物需要付款0.55 元,没有5 角的硬币,只好用2*20+10+5 共4 枚硬币来付款。如果付出1 元,找回4 角5 分,同样需要4 枚硬币。但是如果付出1.05 元(1 枚1元和1 枚5分),找回5 角,只需要3 枚硬币。这个方案用的硬币个数最少。

对于给定的各种面值的硬币个数和付款金额,计算使用硬币个数最少的交易方案。

Input:输入数据有若干组,每一行有6 个整数和1 个有2 位小数的实数。分别表示可以使用的各种面值的硬币个数和付款金额。文件以6 个0 结束。

Output:将计算出的最少硬币个数输出。结果应分行输出,每行一个数据。如果不可能完成交易,则输出"impossible"。

Sample Input:

view sourceprint?1 2 4 2 2 1 0 0.95 

2 2 4 2 0 1 0 0.55 

3 0 0 0 0 0 0

Sample Output:

view sourceprint?1 2 

2 3

解题思路:01背包,完全背包。

change[i]表示商店支付面值为i需要的最少硬币个数;

dp[i]表示顾客现有的硬币数支付面值为i需要的最少硬币数;

w为当前要支付的实际面值,若顾客支付面值为k的钱(k>=w),商家找钱k-w,该条件下最少需要的硬币数为dp[k]+change[k-w],由此推得,最少硬币数为所有符合条件k>=w下最小的dp[k]+change[k-w];

即: ans = min(dp[k]+change[k-w])(k>=w)。

对于change[i],商店里各面值的硬币有足够多,故可用完全背包实现。

对于dp[i],可用混合背包计算,这里我直接拆成01背包来实现(比较暴力,O(∩_∩)O~)。

PS:为减少空间开销,最终化为以5分为单位计算。

view sourceprint?001 #include<stdio.h> 

002 #include<string.h> 

003   

004 const int N = 20000; 

005 int change[N];//change[i]为面值为i的钱至少需要的硬币个数 

006 int dp[N];//dp[i]为当前拥有的硬币数量条件下表示面值为i的最少硬币个数 

007 int value[6] = {1,2,4,10,20,40};//每种硬币对应面值,依次为1,2,4,10,20,40个五分,即5,10,20,50,100,200; 

008 int number[6];//对应于当前拥有的每种硬币个数 

009   

010 void init()//计算change[i] 

011 { 

012    int i,j; 

013    for(i=0;i<N;i++)change[i]=-1; 

014    change[0]=0; 

015    for(i=0;i<6;i++) 

016    { 

017       for(j=value[i];j<N;j++)//这里使用完全背包,不能理解的话可参考背包九讲 

018       { 

019        if(change[j-value[i]]!=-1) 

020        { 

021          int temp=change[j-value[i]]+1; 

022          if(change[j]==-1||temp<change[j])change[j]=temp; 

023        } 

024       } 

025    } 

026 } 

027 int main() 

028 { 

029    //freopen("change.in","r",stdin); 

030      

031     init(); //计算出change[i] 

032    

033     while(scanf("%d%d%d%d%d%d",&number[0],&number[1],&number[2],&number[3],&number[4],&number[5])!=EOF) 

034     { 

035       int sum = 0; 

036       int kk; 

037       for(kk=0;kk<6;kk++)sum+=number[kk]; 

038       if(sum==0)break; 

039       double weight; 

040       scanf("%lf",&weight); 

041       weight=weight*100; 

042      // printf("weight = %lf\n",weight); 

043       int w = int(weight+0.0000001);//处理精度问题 

044       //printf("%d\n",w); 

045   

046       if(w%5!=0)//若不能整除,则无法表示 

047       { 

048          printf("impossible\n"); 

049          continue; 

050       } 

051       else

052           w = w/5; 

053        

054       int i,j; 

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

056       dp[0]=0; 

057       int bigger = 0; 

058       for(i=0;i<6;i++)//计算顾客支付面值i需要的最少硬币数dp[i] 

059       { 

060         while(number[i]--) //将混合背包拆成01背包做,写水了点。。。 

061         { 

062          bigger = bigger+value[i]; 

063          for(j=bigger;j>=value[i];j--) 

064          { 

065           if(dp[j-value[i]]!=-1) 

066           { 

067             int temp=dp[j-value[i]]+1; 

068             if(dp[j]==-1||temp<dp[j]) 

069             { 

070               dp[j]=temp; 

071             } 

072           } 

073          } 

074         } 

075       } 

076    

077     int ans =-1; 

078     for(i=w;i<=bigger;i++)//寻找最少硬币组合 

079     { 

080      if(dp[i]!=-1) 

081      { 

082       int need = i-w; 

083       if(change[need]!=-1) 

084       { 

085        int temp = dp[i]+change[need]; 

086        if(ans==-1||ans>temp)ans=temp; 

087       } 

088      } 

089     } 

090   

091    // for(i=0;i<N;i++) 

092   //   if(dp[i]!=-1) 

093    //  printf("dp[%d]=%d\n",i,dp[i]); 

094   

095     if(ans!=-1) 

096     printf("%d\n",ans); 

097     else

098      printf("impossible\n"); 

099    } 

100    return 0; 

101 }
分享到:
评论

相关推荐

    动态规划求解找零问题和背包问题C++代码

    在这个场景中,我们有两个具体的问题:硬币找零问题和01背包问题,这两个问题都可以通过动态规划来解决,并且都使用了C++语言进行编程。 **一、硬币找零问题** 这个问题的目标是最小化找零所需的硬币数量。给定一...

    最近对,8枚硬币,01背包回溯法,串匹配问题/C++实现,内有报告

    在IT领域,尤其是在算法设计与分析中,"8枚硬币"、"01背包回溯法"和"串匹配问题"是常见的经典问题。这些问题的C++实现可以帮助我们深入理解这些算法的工作原理,并在实际编程中应用。下面将详细讨论这三个知识点。 ...

    ConsoleApplication20_算法设计与分析之动态规划求解硬币问题_

    在这个“算法设计与分析之动态规划求解硬币问题”的案例中,我们将探讨如何使用动态规划方法来解决一个经典的组合优化问题:硬币找零问题。 硬币找零问题的基本设定是这样的:你有一组不同面值的硬币,目标是找出...

    背包问题,动态规划,贪心,回朔源码

    【背包问题】是一种经典的组合优化问题,通常出现在计算机科学和运筹学中。它涉及到在容量有限的背包中选择物品,以最大化总价值或总重量,同时不能超过背包的容量限制。背包问题有许多变种,如完全背包、0-1背包、...

    算法分析与设计 最少硬币问题

    初始状态d[0]为0,因为不需要任何硬币找零0元。 接下来,我们可以使用动态规划的思想来构建解决方案。动态规划的核心是将大问题分解为小问题,然后逐个解决。对于最少硬币问题,我们可以通过以下递推公式来求解: ...

    算法分析与设计实验报告

    在本篇实验报告中,我们将深入探讨算法分析与设计的核心概念,主要关注找零钱问题、伪造硬币问题以及经典的“0-1”背包问题。这些问题都是计算机科学中常见的优化问题,通过解决这些问题,我们可以更好地理解和掌握...

    找零钱问题C++实现 找零钱问题

    根据给定的信息,这里涉及到两个不同的编程问题:第一个是经典的找零钱问题,第二个则是0/1背包问题的一个变种。 ### 找零钱问题 #### 核心思想 找零钱问题通常可以用动态规划来解决。其核心思想是:对于任意一个...

    L1nwatch#interview_collect#找零问题1

    题目找零问题, 给个金额让你找出对应的最小硬币数目背包问题解法?

    五大基本算法及其经典问题,算法数据结构

    例如,硬币找零问题中,贪心地选取面值最大的硬币优先找零;活动选择问题确保最大的活动数量得以执行;多机调度问题和小船过河问题都要求在有限资源下最大化效益;分发饼干问题考虑满足每个人口味的同时最大化满意度...

    贪心算法 (2).pdf

    在动态规划解决硬币找零问题中,程序遍历所有可能的金额,对于每个金额,找出使用最少数量的硬币组合。 最后一个代码片段是关于哈夫曼编码的实现。哈夫曼编码是一种数据压缩方法,利用贪心策略构造最小带权路径长度...

    动态规划经典题12道

    10. **硬币找零问题**:给定不同面额的硬币,求解找零的最少硬币数,dp[i]表示找零i元所需的最少硬币数。 11. **约瑟夫环**:动态规划可以解决约瑟夫环问题,即每隔一定数目的人报数,报到的人出局,最后剩下的人是...

    动态规划经典应用

    dp[i]表示用前i种硬币找零i元所需的最少硬币数。通过迭代更新dp数组,我们可以逐步求解出最优解。关键在于确定状态转移的边界条件和递推公式,如“贪婪策略”在某些情况下可能不适用,而动态规划能确保找到全局最优...

    经典问题算法解法汇总

    这个问题可以用动态规划解决,创建一个状态转移方程来表示用不同面值硬币找零的过程。 总的来说,这个压缩包包含的内容涵盖了算法设计和分析的重要方面,从基本的排序和搜索到更高级的问题解决策略,如动态规划和最...

    找最轻硬币动态规划

    这个问题可以应用于多种情境,如货币找零、背包问题或者最小化成本等。 首先,我们需要理解动态规划的基本概念。动态规划通过将复杂问题分解为更小的子问题来解决,这些子问题的解可以组合成原问题的解。关键在于,...

    具有六种硬币的典型系统在变革问题上的特征_Characterization of canonical systems with

    变革问题的核心在于如何在给定的货币系统中,用最小的硬币数量组合出特定的总金额,这是日常生活中经常需要解决的常见问题,如货币找零。由于变革问题在组合优化中的重要性,它被广泛地应用于计算机算法的设计和分析...

    DP入门_阮行止.pptx

    本课件主要通过一个经典的硬币找零问题来介绍DP的基本概念和应用。 在DP入门中,我们首先面临的问题是:给定一系列不同面值的硬币(如1, 5, 10, 20, 50, 100)以及一个目标金额,我们需要找到最少使用多少枚硬币来...

    动态规划之找零钱问题

    4. **边界情况处理**:如何处理硬币面额大于目标金额的情况,以及没有足够硬币找零的情况。 5. **实例分析**:通过具体的例子解释动态规划表的填充过程,以帮助理解算法工作原理。 6. **拓展应用**:可能还会讨论...

    动态规划算法讲稿 ACM

    9. **实例解析**:例如,经典的“硬币找零”问题,我们可以定义一个二维数组dp[i][j]表示用前i种面额的硬币找零j元的最少硬币数量,通过状态转移方程进行填充,最终得到原问题的答案。 10. **实战应用**:动态规划...

    ACM-ACM-ICPC算法示例之Greedy-题解.zip

    4. 硬币找零问题:给定不同面值的硬币,找到最少的硬币数量来凑成某个金额,贪心策略可以是优先选择面值大的硬币。 5. 时间复杂度优化:在某些动态规划问题中,可以通过贪心策略减少状态转移的计算量,例如求最长...

    dp.rar_DP_visual c

    8. 编程面试题目:如剪绳子、股票买卖、硬币找零问题等,都是DP的典型应用。 使用Visual C++进行DP算法的实现,开发者可以利用IDE的强大调试功能,查看每一步的变量状态,有助于理解算法的运行过程和调试代码。 ...

Global site tag (gtag.js) - Google Analytics