4

重複の可能性:
与えられた金額に最も適したコイン

面接の練習用の質問をいくつか検討していますが、これはいつも私を困惑させてきました。質問は次のとおりです。

与えられたコイン 1c、7c、13c、および 19c は、X の入力を表すために必要な最小数のコインを含む文字列を返します。

さて、以前は 1 セント、5 セント、10 セント、25 セントなどの簡単な金種だったので、これを簡単に解決しました。それは単なる貪欲なアルゴリズムです。これについては、ある種の順列の問題になると考えていますが、最小値を取得する方法がわかりません。何か案は？ここに私が持っているいくつかの疑似コードがあります:

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

このようにすればよいと思います。

金額は×です。コインは1c、7c、13c、19cです。

アルゴリズムは次のとおりです。

x = x*100;

need_19 = x/19;

y = x%19;

need_13 = y/13;

y = y%13;

need_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 などの入力値の場合は 1 秒未満ですが、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コインを使用するか、77 枚少ない1コインを使用できます。貪欲なアルゴリズムは後者のケースを与えます。これは正しいです。なぜなら、71枚のコインを取り除いて 1 枚のコインを追加する方が良いからです7。つまり、コイン数が 6 減ります。

値が 13 から 18 の場合、a13と aは使用できません。これ7は最小値になるため、ミックスまたはミックス20で行き詰まるからです(すべてのコインは前の段落と同じ理由でアウトです - 13 を交換します)。1 枚のコインのコイン数は大幅に減少します)。明らかに、13 の値に対する最善の賭けは 1 枚のコインですが、14 はどちらかまたは(両方とも 2 枚のコイン)で達成できます。次に、15 から 18 までの値は単純にコインが追加されます。13/17/11113137/713/11

同様に、19 の値は単一のコインであり、20 の値はまたは19で表すことができます。21 から 37 までの値 (38の値の直前) は、前の 3 つの段落からの最小ミックスを加えたものです。19/113/719/1919

したがって、選択された値 (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 に答える