2

各金種の硬貨の数が無限である硬貨交換問題のアルゴリズムのアイデアを知りたいです。DPを適用する方法を意味します（標準のコイン交換問題のように）たとえば、セット1、10、15の場合、35の変更で--10の2コインと15の1コイン

また、このためのブルートフォーシングアルゴリズムのアイデアを教えてください。私はすべてのセットを繰り返すことを知っています。しかし、ブルートフォース中に各コインの数を変える方法

4

5 に答える 5

7

帰納的に、一度に1ステップずつソリューションを構築することを考えます。

利用可能なコインは1c、5c、10c、25cです（必要に応じて微調整できます）

  1. 1cの最小コイン=1X1c。4セントまでは、最低額の1cコインが必要です。
  2. 5セントで5セント硬貨が1枚あります。これを上記の4cと組み合わせると、1から9までの任意の数を生成できます。
  3. 10セントの場合、1X10cが必要です。上記の3つを組み合わせると、1から19までの任意の数を生成できます。
  4. 20cの場合、20は10で割り切れるので、2x10cが必要です。

問題を帰納的に定式化できれば、それに取り組む方が簡単かもしれません。

編集：
了解しました。動的計画法ソリューションを説明する別の試みがあります。

x行（x異なる金種の数）nと列（n最小の金種を使用して作成する必要のある量）を持つテーブルについて考えてみてください。この表のすべてのセルは、個別のサブ問題を表しており、最終的にはその解決策が含まれます。推定：

行1はセットを表し{1c}ます。つまり、行1では無限に使用できます。1c
行2はセットを表し{1c, 10c}ます。つまり、行2では無限1cになり、10c
行3はセット{1c, 10c, 15c}を表します。
各列は作成する量を表します。 。

したがって、すべてのセルは1つの小さなサブ問題に対応します。たとえば（簡単にするために、インデックスは1から始まります）、
cell(1, 5)==>5cのみを使用して構築{1c}
cell(2, 9)== >9cを使用して構築==>を使用して{1c, 10c}
cell(3, 27)構築これで、次 の答えを得ることが目的です。27c{1c, 10c, 15c}
cell(x, n)

Solution:
最も単純な問題からテーブルの解決を開始します。最初の行で使用可能な唯一の金種はであるため、最初の行を解くのは簡単です{1c}。行1のすべてのセルには自明な解があり、cell(1, n)= {nx1c}（nのコイン1c）になります。

次の行に進みます。2行目を一般化して、（たとえば）を解く方法を見てみましょう。つまり、を使用してcell(2, 28)構築します。ここで、ソリューションに含めるかどうか、およびコインの数を決定する必要があります。3つの選択肢があります（3 = 28/10 + 1）28c{1c, 10c}10c

Choice 1：前の行（に格納されている）から残りを取得し
ます。これはあなたに=を与えます{1x10c}cell(1, 18){1x10c, 18x1c}19 coins

Choice 2：前の行（に格納されている）から残りを取得し
ます。これはあなたに=を与えます{2x10c}cell(1, 8){2x10c, 8x1c}10 coins

Choice 3：
no10cを取り、残りを前の行（に格納されているcell(1, 28)）から取得します。これはあなたに{28x1c}=を与えます28 coins

明らかに、コインが少なくて済むので、選択肢2が最適です。それを表に書き留めて、先に進んでください。テーブルは、一度に1行ずつ、行内で、量が増える順に入力されます。

上記のルールに従うと、に到達しますcell(x, n)。これに対する解決策は、選択肢から選択することになります。n/p + 1ここで、p=行の最新の額面金額xです。最良の選択はあなたの答えです。

この表は、実際には小さな問題の解決策を記憶しているため、何度も解決する必要はありません。

于 2009-10-05T09:33:03.363 に答える
3

強引な部分について：

int i,j,k;
for(i=0;i<35;i++){
  for(j=0;j<4;j++){
    for(k=0;k<3;k++){
      if(1*i+10*j+15*k == 35){
        //is this what you need?
        //minimum=min(minimum,(i+j+k));
      }
    }
  }
}
于 2009-10-05T09:17:33.053 に答える
0

強引な力について。

これは「欲張りアルゴリズム」と呼ばれ、表現する必要のある値を超えない最大のコインを常に使用します。

擬似コードは、それぞれを無限に使用できる場合、値を表すために必要なコインの数を返します

int[] greedy(int value, int[] coins) {
   int[] ans = ...;
   int v = coins.length - 1;
   int left = value;
   while (left > 0 && v >= 0) {
       if (coins[v] <= left) {
           ans.push(coins[v]);
       } else { 
           v--;
       }
   }
   return left == 0 ? ans : //representation impossible, 
                            //so you better do something;
}

擬似コードは、それぞれを無限に使用できる場合、値を表すために必要なコインの数を返します

int f(int value, int[] coins) {
   int[] memo = new int[value + 1];
   Arrays.fill(memo, 1234567);
   memo[0] = 0;
   for (int coin : coins)
       for (int i = 0; i + coin <= value; i++)
           memo[i + coin] = min(memo[i + coin], memo[i] + 1);
   return memo[value];
}

どのコインを取るかを知るには、最後から始めif memo[value] = 3ます。次に、すべてのコインをチェックして、そのようなコインを見つけ、に到達するまでmemo[value - coin] == 2続けます。(value - coin)0

于 2009-10-05T11:51:55.063 に答える
0

これは、ある記数法から別の記数法に番号を変換する方法です。例えば：

35 = 1*2^5 + 0*2^4 + 0*2^3 + 0*2^2 + 0*2^1 + 1*2^0

あれは：

var cash = 35;
var coins = [15, 10, 5, 1];
var change = {};
for(var i=0; i<coins.length; i++){
  change[coins[i]]  = Math.floor(cash/coins[i]);
  cash %= coins[i];
}
//change now contains:
//15:2, 10:0, 5:1, 1:0
于 2009-10-05T12:01:37.930 に答える
0

ここで実行できますhttp://www.exorithm.com/algorithm/view/coin_change

function coin_change ($amount, $coins)
{
  $change = array();
  rsort($coins);
  for($i=0; $i<count($coins); $i++) {
    $change[$coins[$i]] = floor($amount/$coins[$i]);
    $amount = $amount % $coins[$i];
  }
  return $change;
}
于 2010-11-02T19:34:57.280 に答える