我正在制作一款游戏，其中包含面额为 10 美元、5 美元、3 美元和 1 美元的硬币。玩家可以在他的库存中拥有 0 个或更多的每种货币，总共最多 15 个硬币。我想弄清楚如何正确选择硬币，以便提供最少的零钱作为返回。起初我认为这很容易解决，但现在我无法解决这个问题。
这里有两个例子可以进一步解释这种情况:
示例 1:
用户持有这些硬币:5 美元、3 美元、3 美元、3 美元、1 美元、1 美元、1 美元、1 美元，并想以 12 美元的价格购买一件商品。解决方案是支付 5 美元、3 美元、3 美元、1 美元并且不找零。
示例 2:
用户没有任何 1 美元硬币，并且携带 5 美元、3 美元、3 美元、3 美元、3 美元。一件商品以 12 美元的价格购买，因此他们支付 5 美元、3 美元、3 美元和 3 美元，并退还 2 美元的零钱。
由于我们首先选择较大的硬币，我无法弄清楚的是如何知道玩家的库存中是否有足够的较低值(value)的硬币(在本例中为 1 美元)来容纳示例 1，如果没有足以使用示例 2 中更多值(value)更高的硬币。
在下面的示例中可以看到另一个问题，尽管我很乐意让上面的两个示例正常工作:
示例 3: 用户携带这些硬币:5 美元、3 美元、3 美元、3 美元。玩家花 6 美元买了东西。最好使用 $3 和 $3 并且不找零，而不是使用 $5 和 $3 并给出 $2 找零。
我相信前两个示例可以使用递归和贪婪算法的变体来解决。
对于赏金奖励:
我在下面添加了我自己的答案作为目前的临时解决方案。但是，我喜欢下面 Llama 先生的方法(请参阅他引用的链接)，并希望找到一个 PHP 示例来满足此要求。我相信这种方法不需要递归并使用内存。
如果零钱最少的选项有多个选项，那么我希望用最少的硬币支付的那个平局。
最佳答案
问题可以定义为:
Return a subset of items where the sum is closest to x, but >= x.
这个问题叫做子集和问题。它是 NP 完全的。您找不到在伪多项式时间内运行的完美算法，只有不完美的启发式算法。
但是，如果硬币的数量很少，那么对解空间进行穷举搜索肯定会奏效。
如果硬币数量较多，那么你应该看看维基百科的概况:https://en.wikipedia.org/wiki/Subset_sum_problem#Polynomial_time_approximate_algorithm
关于php - 选择最少或没有零钱的硬币，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/33992049/
我好像记得Lua有类似Ruby的method_missing的东西。还是我记错了？ 最佳答案 表的metatable的__index和__newindex可以用于与Ruby的method_missing相同的效果。 关于ruby-难道Lua没有和Ruby的method_missing相媲美的东西吗？，我们在StackOverflow上找到一个类似的问题： https://stackoverflow.com/questions/7732154/
我有一个奇怪的问题:我在rvm上安装了rubyonrails。一切正常，我可以创建项目。但是在我输入“railsnew”时重新启动后，我有“程序'rails'当前未安装。”。SystemUbuntu12.04ruby-v"1.9.3p194"gemlistactionmailer(3.2.5)actionpack(3.2.5)activemodel(3.2.5)activerecord(3.2.5)activeresource(3.2.5)activesupport(3.2.5)arel(3.0.2)builder(3.0.0)bundler(1.1.4)coffee-rails(
我想在一个没有Sass引擎的类中使用Sass颜色函数。我已经在项目中使用了sassgem，所以我认为搭载会像以下一样简单:classRectangleincludeSass::Script::FunctionsdefcolorSass::Script::Color.new([0x82,0x39,0x06])enddefrender#hamlengineexecutedwithcontextofself#sothatwithintemlateicouldcall#%stop{offset:'0%',stop:{color:lighten(color)}}endend更新:参见上面的#re
大家好!我想知道Ruby中未使用语法ClassName.method_name调用的方法是如何工作的。我头脑中的一些是puts、print、gets、chomp。可以在不使用点运算符的情况下调用这些方法。为什么是这样？他们来自哪里？我怎样才能看到这些方法的完整列表？ 最佳答案 Kernel中的所有方法都可用于Object类的所有对象或从Object派生的任何类。您可以使用Kernel.instance_methods列出它们。 关于没有类的Ruby方法？，我们在StackOverflow
我真的为这个而疯狂。我一直在搜索答案并尝试我找到的所有内容，包括相关问题和stackoverflow上的答案，但仍然无法正常工作。我正在使用嵌套资源，但无法使表单正常工作。我总是遇到错误，例如没有路线匹配[PUT]"/galleries/1/photos"表格在这里:/galleries/1/photos/1/edit路线.rbresources:galleriesdoresources:photosendresources:galleriesresources:photos照片Controller.rbdefnew@gallery=Gallery.find(params[:galle
状态:我正在构建一个应用程序，其中需要一个可供用户选择颜色的字段，该字段将包含RGB颜色代码字符串。我已经测试了一个看起来很漂亮但效果不佳的。它是“挑剔的颜色”，并托管在此存储库中:https://github.com/Astorsoft/picky-color.在这里我打开一个关于它的一些问题的问题。问题:请建议我在Rails3应用程序中使用一些颜色选择器。 最佳答案 也许页面上的列表jQueryUIDevelopment:ColorPicker为您提供开箱即用的产品。原因是jQuery现在包含在Rails3应用程序中，因此使用基
我在Rails应用程序中使用CarrierWave/Fog将视频上传到AmazonS3。有没有办法判断上传的进度，让我可以显示上传进度如何？ 最佳答案 CarrierWave和Fog本身没有这种功能；你需要一个前端uploader来显示进度。当我不得不解决这个问题时，我使用了jQueryfileupload因为我的堆栈中已经有jQuery。甚至还有apostonCarrierWaveintegration因此您只需按照那里的说明操作即可获得适用于您的应用的进度条。 关于ruby-on-r
如何在Ruby中获取BasicObject实例的类名？例如，假设我有这个:classMyObjectSystem我怎样才能使这段代码成功？编辑:我发现Object的实例方法class被定义为returnrb_class_real(CLASS_OF(obj));。有什么方法可以从Ruby中使用它？ 最佳答案 我花了一些时间研究irb并想出了这个:classBasicObjectdefclassklass=class这将为任何从BasicObject继承的对象提供一个#class您可以调用的方法。编辑评论中要求的进一步解释:假设你有对象
我在非Rails项目中使用ActiveRecord。在Rails中，我可以这样做:config.time_zone='EasternTime(US&Canada)'config.active_record.default_timezone='EasternTime(US&Canada)'但如果我不使用rails，我该如何设置时区？ 最佳答案 ActiveRecord::Base.default_timezone='EasternTime(US&Canada)' 关于ruby-没有轨道的A
在我让另一个人重做我的前端UI之前，我的Rails应用程序运行平稳。我已经尝试解决此错误3天了。这是错误:Nosuchfileordirectory-identifyExtractedsource(aroundline#59):575859606162@post=Post.find(params[:id])authorize@postif@post.update_attributes(post_params)flash[:notice]="Postwasupdated."redirect_to[@topic,@post]else{"utf8"=>"✓","_method"=>"patc