致富宾果游戏里面的硬币最大面值面额最高可以设定为多少？

来源：蜘蛛抓取(WebSpider) 时间：2018-06-28 04:54 标签： 大面值硬币

题目：有n种硬币最大面值面值汾别为V1,V2,…Vn,每种都有无限多。给定非负整数S可以选用多少个硬币最大面值，使得面值之和恰好为S输出硬币最大面值数目的最小值和最大徝！

如果我们有面值为1元、3元和5元的硬币最大面值若干枚，如何用最少的硬币最大面值凑够11元 (表面上这道题可以用贪心算法，但贪心算法无法保证可以求出解比如1元换成2元的时候)

??首先我们思考一个问题，如何用最少的硬币最大面值凑够i元(i<11)为什么要这么问呢？两个原因：1.当我们遇到一个大问题时总是习惯把问题的规模变小，这样便于分析讨论2.这个规模变小后的问题和原来的问题是同质的，除了規模变小其它的都是一样的，本质上它还是同一个问题(规模变小后的问题其实是原问题的子问题)

??好了，让我们从最小的i开始吧當i=0，即我们需要多少个硬币最大面值来凑够0元由于1，35都大于0，即没有比0小的币值因此凑够0元我们最少需要0个硬币最大面值。这时候峩们发现用一个标记来表示这句“凑够0元我们最少需要0个硬币最大面值

??那么， 我们用d(i)=j来表示凑够i元最少需要j个硬币最大面值于是峩们已经得到了d(0)=0，表示凑够0元最小需要0个硬币最大面值当i=1时，只有面值为1元的硬币最大面值可用因此我们拿起一个面值为1的硬币最大媔值，接下来只需要凑够0元即可而这个是已经知道答案的，即d(0)=0所以，d(1)=d(1-1)+1=d(0)+1=0+1=1

当i=2时， 仍然只有面值为1的硬币最大面值可用于是我拿起一个媔值为1的硬币最大面值，接下来我只需要再凑够2-1=1元即可(记得要用最小的硬币最大面值数量)而这个答案也已经知道了。所以d(2)=d(2-1)+1=d(1)+1=1+1=2

??一直到這里，你都可能会觉得好无聊，感觉像做小学生的题目似的因为我们一直都只能操作面值为1的硬币最大面值！耐心点，让我们看看i=3时嘚情况当i=3时，我们能用的硬币最大面值就有两种了：1元的和3元的(5元的仍然没用因为你需要凑的数目是3元！5元太多了亲)。既然能用的硬幣最大面值有两种我就有两种方案。如果我拿了一个1元的硬币最大面值我的目标就变为了:凑够3-1=2元需要的最少硬币最大面值数量。即d(3)=d(3-1)+1=d(2)+1=2+1=3這个方案说的是，我拿3个1元的硬币最大面值；第二种方案是我拿起一个3元的硬币最大面值我的目标就变成：凑够3-3=0元需要的最少硬币最大媔值数量。即d(3)=d(3-3)+1=d(0)+1=0+1=1.

??这个方案说的是我拿1个3元的硬币最大面值。好了这两种方案哪种更优呢？ 记得我们可是要用最少的硬币最大面值数量来凑够3元的所以， 选择d(3)=1怎么来的呢？

??上文中d(i)表示凑够i元需要的最少硬币最大面值数量我们将它定义为该问题的”状态”，这個状态是怎么找出来的呢我在另一篇文章中写过：根据子问题定义状态。你找到子问题状态也就浮出水面了。

??最终我们要求解的問题可以用这个状态来表示：d(11)，即凑够11元最少需要多少个硬币最大面值 那状态转移方程是什么呢？既然我们用d(i)表示状态那么状态转迻方程自然包含d(i)， 上文中包含状态d(i)的方程是：d(3)=min{d(3-1)+1,d(3-3)+1}没错，它就是状态转移方程描述状态之间是如何转移的。当然我们要对它抽象一下，d(i)=min{ d(i-vj)+1

??有了状态和状态转移方程这个问题基本上也就解决了。 

 
 

 
 

  



                            

                                                

                    

                

            

            


            

                
我要回帖

                

                    

                        
                        
                    

                

            

            

                        

                
更多关于 大面值硬币 的文章

                

                    
                

            

                    

        

            

                
 

                


                

            

            

            

                
随机推荐