确定硬币组合的算法

Question

我最近面临一个编程算法的提示,我不知道该怎么做.我以前从来没有真正写过算法,所以我对此有点新意.

问题是写一个程序,以确定收银员根据硬币值和硬币数量作为变化回馈所有可能的硬币组合.例如,可能有一个有4个硬币的货币:2美分,6美分,10美分和15美分硬币.这有多少组合等于50美分？

我正在使用的语言是C++,虽然这并不重要.

编辑:这是一个更具体的编程问题,但我如何分析C++中的字符串来获取硬币值？它们是在文本文档中给出的

4 2 6 10 15 50 

(在这种情况下,数字对应于我给出的例子)

Answer 1

这个问题众所周知是硬币变化问题.请检查这与此有关详情.此外,如果你谷歌"硬币改变"或"动态编程硬币改变",那么你将获得许多其他有用的资源.

Answer 2

这是Java中的递归解决方案:

// Usage: int[] denoms = new int[] { 1, 2, 5, 10, 20, 50, 100, 200 };       
// System.out.println(ways(denoms, denoms.length, 200));
public static int ways(int denoms[], int index, int capacity) {
    if (capacity == 0) return 1;
    if (capacity < 0 || index <= 0 ) return 0;
    int withoutItem = ways(denoms, index - 1, capacity); 
    int withItem = ways(denoms, index, capacity - denoms[index - 1]); 
    return withoutItem + withItem;
}

Answer 3

这似乎有点像分区,除了你不在1:50使用所有整数.它似乎也与bin打包问题类似,略有不同:

• 维基百科:分区(数论)
• 维基百科:Bin包装问题
• Wolfram Mathworld:Partiton

实际上,在考虑它之后,它是一个ILP,因此NP难.

我建议一些动态编程appyroach.基本上,您可以定义一个值"余数"并将其设置为您的目标(例如,50).然后,在每一步,您都会执行以下操作:

1. 弄清楚剩下的最大硬币是什么
2. 考虑如果您(A)包括该硬币或(B)不包括该硬币会发生什么.
3. 对于每个场景,递归.

因此,如果余数为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, Coinset = 0x25, 0x10

每个分支将分成两个分支,除非:

• 余数为0(在这种情况下你会记录它)
• 剩余部分小于最小的硬币(在这种情况下你会丢弃它)
• 没有剩下的硬币(在这种情况下,你会丢弃它,因为剩余的!= 0)