我最近面临着一个编程算法的提示,我不知道该怎么做.我从来没有真正写过一个算法,所以我是一个这样的新手.
问题是写一个程序,以确定收银员的所有可能的硬币组合,作为基于硬币值和硬币数量的变化作为替代.例如,可能有一个4个硬币的货币：2分,6分,10分和15分硬币.有多少组合等于50美分？
我使用的语言是C,尽管这并不重要.
编辑：这是一个更具体的编程问题,但是如何分析C中的字符串来获取硬币值？他们在文本文档中给出了
4 2 6 10 15 50
(这里的数字对应于我给出的例子)
解决方法
这似乎有点像分区,除了你在1:50中不使用所有的整数.它也似乎类似于bin包装问题,略有不同：
> Wikipedia: Partition (Number Theory)
> Wikipedia: Bin packing problem
> Wolfram Mathworld: Partiton
其实在考虑之后,是an ILP,NP-hard.
我建议一些动态的编程appyroach.基本上,您将定义一个值“余数”,并将其设置为您的目标(例如50).然后,在每一步,您将执行以下操作：
找出可以适合剩下的最大的硬币
>考虑如果你(A)包括硬币或(B)不包括那个硬币会发生什么.
>对于每个场景,递归.
所以如果剩余的是50,最大的硬币是25和10,你会分两种情况：
1. Remainder = 25,Coinset = 1x25 2. Remainder = 50,Coinset = 0x25
下一步(每个分支)可能如下所示：
1-1. Remainder = 0,Coinset = 2x25 <-- Note: Remainder=0 => Logged 1-2. Remainder = 25,Coinset = 1x25 2-1. Remainder = 40,Coinset = 0x25,1x10 2-2. Remainder = 50,0x10
每个分支将分成两个分支,除非：
>剩下的是0(在这种情况下你会记录它)>剩下的是小于最小的硬币(在这种情况下你会丢弃它)>没有更多的硬币留下(在这种情况下,你会丢弃它,因为剩余！= 0)
