有极速快乐十分吗|极速快乐十分走势图|

关于背包的硬币找零问题

解题思路:01背包,完全背包
服务器君一?#19981;?#36153;了116.539 ms进行了5?#38382;?#25454;库查询,努力地为您提供了这个页面。
试试阅读模式?希望听取您的建议

设有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?#33322;?#35745;算出的最少硬币个数输出。结果应分行输出,每行一个数据。如果不可能完成交易,则输出"impossible"。

Sample Input:

2 4 2 2 1 0 0.95
2 4 2 0 1 0 0.55
0 0 0 0 0 0

Sample Output:

2
3

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

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

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

w为当前要支付的?#23548;?#38754;值,若顾客支付面值为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],可用混合背包计算,这里我直?#30828;?#25104;01背包来实现(比较暴力,O(∩_∩)O~)。

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

#include<stdio.h>
#include<string.h>
const int N = 20000;
int change[N];//change[i]为面值为i的钱至少需要的硬币个数
int dp[N];//dp[i]为当前拥有的硬币数量条件下表示面值为i的最少硬币个数
int value[6] = {1,2,4,10,20,40};//每种硬币对应面值,?#26469;?#20026;1,2,4,10,20,40个五分,即5,10,20,50,100,200;
int number[6];//对应于当前拥有的每种硬币个数
void init()//计算change[i]
{
   int i,j;
   for(i=0;i<N;i++)change[i]=-1;
   change[0]=0;
   for(i=0;i<6;i++)
   {
      for(j=value[i];j<N;j++)//这里使用完全背包,不能理解的话可参考背包九讲
      {
       if(change[j-value[i]]!=-1)
       {
         int temp=change[j-value[i]]+1;
         if(change[j]==-1||temp<change[j])change[j]=temp;
       }
      }
   }
}
int main()
{
   //freopen("change.in","r",stdin);
   
    init(); //计算出change[i]
 
    while(scanf("%d%d%d%d%d%d",&number[0],&number[1],&number[2],&number[3],&number[4],&number[5])!=EOF)
    {
      int sum = 0;
      int kk;
      for(kk=0;kk<6;kk++)sum+=number[kk];
      if(sum==0)break;
      double weight;
      scanf("%lf",&weight);
      weight=weight*100;
     // printf("weight = %lfn",weight);
      int w = int(weight+0.0000001);//处理精度问题
      //printf("%dn",w);
      if(w%5!=0)//若不能整除,则无法表示
      {
         printf("impossiblen");
         continue;
      }
      else
          w = w/5;
     
      int i,j;
      memset(dp,-1,sizeof(dp));
      dp[0]=0;
      int bigger = 0;
      for(i=0;i<6;i++)//计算顾客支付面值i需要的最少硬币数dp[i]
      {
        while(number[i]--) //将混合背包拆成01背包做,写水了点。。。
        {
         bigger = bigger+value[i];
         for(j=bigger;j>=value[i];j--)
         {
          if(dp[j-value[i]]!=-1)
          {
            int temp=dp[j-value[i]]+1;
            if(dp[j]==-1||temp<dp[j])
            {
              dp[j]=temp;
            }
          }
         }
        }
      }
 
    int ans =-1;
    for(i=w;i<=bigger;i++)//寻找最少硬币组合
    {
     if(dp[i]!=-1)
     {
      int need = i-w;
      if(change[need]!=-1)
      {
       int temp = dp[i]+change[need];
       if(ans==-1||ans>temp)ans=temp;
      }
     }
    }
   // for(i=0;i<N;i++)
  //   if(dp[i]!=-1)
   //  printf("dp[%d]=%dn",i,dp[i]);
    if(ans!=-1)
    printf("%dn",ans);
    else
     printf("impossiblen");
   }
   return 0;
}

本文地址:http://www.bavugt.tw/librarys/veda/detail/844,欢迎访问原出处。

不打个分吗?

转载随意,但请带上本文地址:

http://www.bavugt.tw/librarys/veda/detail/844

如果你认为这篇文章值得更多人阅读,欢迎使用下面的分享功能。
小提示:您可以按快捷键 Ctrl + D,或点此 加入收藏

阅读一百本计算机著作吧,少年

很多人觉得自己技术进步很慢,学习效?#23454;停?#25105;觉得一个重要原因是看的书少了。多少是多呢?起码?#27599;?、4、5、6米吧。给个具体的数量,那就100本书吧。很多人知识结构不好而且不?#20302;常?#22240;为在特定领域有一个足够量的知?#35835;?足够良好的知识结构,?#20302;?#21270;以后就足以应对大量未曾遇到过的问题。

奉劝自学者:构建特定领域的知识结构体系的路径中再也没有比学?#26696;?#19987;业的专业课程更好的了。如果我的知识结构体系足以?#20381;?#38754;试官的大部分甚至吞并他的知识结构体系的话,读到他言语中的一个词我们就已经知?#28010;?#35201;表达什么,我们可以让他坐“上位?#21271;暇顾?#26159;面试官,但是在知识结构体系以及心理上我们就居高临下。

所以,阅读一百本计算机著作吧,少年!

《深入理解MySQL核心技术》 Sasba Pacbev (作者), 李芳 (译者), 于红芸 (译者), 邵健 (译者)

《深入理解MySQL核心技术》:从公共可用性的意义上讲,MySQL源代码是开放源代码,但如果对其不了解,则实质?#24076;?#23427;对于您来说是封闭的。MysQL开发团队的前成员Sasha Pachev通过《深入理解MySQL核心技术》给出了MySQL 5的全面指?#24076;?#25581;示了这一强大数据库的内部运作。您将直奔MySQL核心技术,了解各种数据结?#36141;?#21508;种方便的功能的运作情况,了解如何添?#26377;?#30340;存储引擎和配置选项?#21462;?《深入理解MySQL核心技术》从结构概况讲起,在这一部分解释了MysQL的不同组件是如何协同工作的。接着将学习设置有效的可编译代码副本的步骤,然后使用基本架构添加自己的配置变量和存储引擎。

更多计算机宝库...

有极速快乐十分吗
广东快乐十分最快开奖一定牛 白姐透码 新疆时时彩后三基本走势图 uu自动挂机赚钱软件 天津快乐十分走势图表 时时彩之家江苏11选5 北京pk10数理分析论坛 骨牌牌九游戏单机下载 金福彩票安卓 云南快乐10分钟走势图