4

可能重复：
最适合给定金额的硬币

我正在复习一些练习面试问题，这个问题一直让我感到困惑。这是问题：

给定硬币 1c、7c、13c 和 19c 返回一个字符串，其中所需硬币的数量最少 > 以表示 X 的输入。

现在，当它使用 1c、5c、10c 和 25c 等简单面额时，我已经很容易地解决了这个问题。这只是一个简单的贪心算法。为此，我认为这将是某种排列问题，但我不确定如何获得最小值。有任何想法吗？这是我拥有的一些伪代码：

String coinDenominations(double amount, String coins)
{
    if(amount > .19) coinDenominations(amount - .19, coins + "19 ");
    if(amount > .13) coinDenominations(amount - .13, coins + "13 ");
    if(amount > .07) coinDenominations(amount - .07, coins + "7 ");
    if(amount > .01) coinDenominations(amount - .01, coins + "1 ");
    if(amount == 0) System.out.println(coins);
}

我对排列很生疏，但我认为这会输出可能的组合。我怎么会找到最小的金额呢？有没有更好的非递归方式来做到这一点？

4

3 回答 3

0

我认为可以这样做。

金额为 x。硬币是 1c、7c、13c 和 19c。

算法如下。

x = x*100；

需要_19 = x/19；

y = x%19;

需要_13 = y/13；

y = y%13;

需要_7 = y/7；

y = y%7;

需要_1 = y;

total_coins = need_19 + need_13 + need_7 + +need_1；

于 2012-10-16T05:47:24.807 回答
0

我想我们可以这样写：

String coinDenominations(double amount){
   int[] coinDenom = new int[] {19,13,7,1};
   int amountInCents = amount*100;
   String coinDenomString = "";
   for(int i=0; i< coinDenom.length; i++){
       coinDenomString = coinDenomString + ((int)(amountInCents/coinDenom[i])) 
                         + "of +"  coinDenom[i] + "coins";
       amountInCents = amountInCents % coinDenom[i];
   }
   return coinDenomString;
}

我相信，上面也可以转换为递归。

于 2012-10-16T06:03:58.077 回答
0

正如这个答案中提到的，某些硬币组合可能适合贪婪算法，但不能保证贪婪会给你所有硬币组合的最佳组合。

下面是 Python（一种理想的伪代码语言）中的详尽递归解决方案。

请注意，这为您提供了排列而不是组合，但是，如果您想过滤掉重复项（就组合而言），则在创建列表后进行排序和过滤会很简单。

另请注意，对于较大的金额，这可能会相当可怕。例如，虽然像 27 或 75 这样的输入值不到一秒，但输入 1024 至少需要几分钟才能让我感到无聊并取消它）。

import sys

oldcount = 99999999
lst = []

def recurse (str, amt, count):
    global oldcount
    global lst
    if amt < 0: return
    if count > oldcount: return
    if amt == 0:
        if count < oldcount:
            print "====="
            lst = []
            oldcount = count
        if count == oldcount:
            lst.append (str)
        return
    recurse ("%s 19" % str, amt - 19, count + 1)
    recurse ("%s 13" % str, amt - 13, count + 1)
    recurse ("%s  7" % str, amt -  7, count + 1)
    recurse ("%s  1" % str, amt -  1, count + 1)

recurse ("", int (sys.argv[1]), 0)
#for seq in lst: print seq
print "%d permutations" % len (lst)

请注意，对于面额{1, 7, 13, 19}（这种特殊情况），贪心算法是最好的，其“证明”如下(a)：

对于 1 到 6 的任何值，你必须使用那么多1硬币，这就是贪心算法给你的。

对于 7 到 12 的任何值，您可以使用那么多1硬币7或少 7 个1硬币。贪心算法为您提供后一种情况，这是正确的，因为最好拿走七个1硬币并添加一个7硬币 - 它会使硬币数量减少六。

对于 13 到 18 的值，您不能使用 a13和 a 7，因为这将是最小值，20因此您会陷入13/1混合或7/1混合（所有1硬币都因与上一段中相同的原因而出局 - 交换 131一个硬币的13硬币是一个巨大的减少）。显然，13 值的最佳投注是单枚13硬币，但 14 可以用一个7/7或13/1（两个硬币）来实现。然后值 15 到 18 只需1添加硬币。

类似地，19 值是单个硬币19，而 20 值可以用19/1或表示13/7。从 21 到 37 的值（就在19/1938 的值之前）19加上前三段的最小组合。

因此，由于选择的值（1并且7是不同的，7/7== 13/1，7/7/7== 19/1/1，13/7==19/1等等），贪心算法工作得很好（我不相信这些值是随机选择的，这太方便了）。

最小硬币计数表如下：

Value  Count  Possibilities
    1      1  1
    2      2  1x2
    3      3  1x3
    4      4  1x4
    5      5  1x5
    6      6  1x6
    7      1  7
    8      2  7,1
    9      3  7,1x2
    :
   12      6  7,1x5
   13      1  13
   14      2  13,1 or 7x2
   15      2  13,1x2 or 7x2,1
    :
   18      6  13,1X5 or 7x2,1x4
   19      1  19
   20      2  19,1 or 13,7
   21      3  19,1x2 or 13,7,1 or 7x3
    :

等等。

(a)不是正式的证明，但我很确定我是对的，我会向第一个向我展示反例的人投票 20 个问题/答案（当然，前提是问题和答案不是完全垃圾- 我必须认为它们很有用，以免破坏投票过程）。

于 2012-10-16T06:05:11.183 回答