合計のコインの最小数S

Question

N個のコインのリスト、それらの値（V1、V2、...、VN）、および総合計Sが与えられます。コインの最小数をS（私たちが望むような種類のコインをいくつでも使うことができます）か、Sまでの合計でコインを選択することはできないと報告します。

私はダイナミックプログラミング、ヘブンそれは分かりませんでした。私は与えられた説明を理解していないので、多分あなたは私にこの仕事をどのようにプログラムするためのヒントを投げ捨てることができますか？コードなし、ちょうど私が始めるべきアイデア。

ありがとうございました。

Answer 1

これは古典的なナップザック問題であり、いくつかの詳細については、こちらを見てみましょう：Wikipedia Knapsack Problem

また、特に最大級から最小値に並べ替え、いくつかの並べ替えをご覧ください。

Answer 2

私はあなたが欲しいのアプローチは次のようだと思う：

あなたは合計Sを生産したいことを知っています。 Sを生産する唯一の方法は、最初にS-V1を生産し、次に値V1のコインを追加することです。またはS-V2を生成し、次に値V2のコインを追加する。または...ターンで

、T=S-V1が戻ってこのようにステッピングすることによりT-V1、またはT-V2、または...

から製造可能である、あなたはあなたのからSを生産するための最良の方法を、もしあれば、決定することができますV s。

Answer 3

動的プログラミングについてはわかりませんが、これは私がやる方法です。ゼロから始まってSに進んでください。 1つのコインでセットを作り、そのセットで2つのコインセットを生産するなど... Sを検索し、Sより大きいすべての値を無視します。それぞれの値について、使用されたコインの数を覚えておいてください。

Answer 4

この問題に対する正確な答えは、ここで詳しく説明されています。 http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=dynProg

Answer 5

多くの人が既に質問に回答しています。ここでは、DPを使用するコード

public static List<Integer> getCoinSet(int S, int[] coins) { 
    List<Integer> coinsSet = new LinkedList<Integer>(); 
    if (S <= 0) return coinsSet; 

    int[] coinSumArr = buildCoinstArr(S, coins); 

    if (coinSumArr[S] < 0) throw new RuntimeException("Not possible to get given sum: " + S); 

    int i = S; 
    while (i > 0) { 
     int coin = coins[coinSumArr[i]]; 
     coinsSet.add(coin); 
     i -= coin; 
    } 

    return coinsSet; 
} 

public static int[] buildCoinstArr(int S, int[] coins) { 
    Arrays.sort(coins); 
    int[] result = new int[S + 1]; 

    for (int s = 1; s <= S; s++) { 
     result[s] = -1; 
     for (int i = coins.length - 1; i >= 0; i--) { 
      int coin = coins[i]; 
      if (coin <= s && result[s - coin] >= 0) { 
       result[s] = i; 
       break; 
      } 
     } 
    } 

    return result; 
} 

Answer 6

すでに指摘したように、動的プログラミングはこの問題に最も適しています。私はこのためにPythonプログラムを書かれている： - ：

12 2 3 5

は、出力は次のようになります。入力の場合

def sumtototal(total, coins_list): 
    s = [0] 
    for i in range(1, total+1): 
     s.append(-1) 
     for coin_val in coins_list: 
      if i-coin_val >=0 and s[i-coin_val] != -1 and (s[i] > s[i-coin_val] or s[i] == -1): 
       s[i] = 1 + s[i-coin_val] 

    print s 
    return s[total] 

total = input() 
coins_list = map(int, raw_input().split(' ')) 
print sumtototal(total, coins_list) 

[0, -1, 1, 1, 2, 1, 2, 2, 2, 3, 2, 3, 3] 3 list_index必要な合計値でありますlist_indexはnoです。その総額を得るために必要なコインの数。上記の入力（値12を得る）に対する答えは3（値5,5,2のコイン）です。

Answer 7

質問にはすでに回答していますが、私が書いた作業用のCコードを提供したいと思います。enter code here

コードにはハードコードされた入力がありますが、単純にしておくだけです。最終的な解は、各和に必要なコインの数を含む配列minです。

#include"stdio.h" 
#include<string.h> 

int min[12] = {100}; 
int coin[3] = {1, 3, 5}; 

void 
findMin (int sum) 
{ 
    int i = 0; int j=0; 
    min [0] = 0; 

    for (i = 1; i <= sum; i++) { 
     /* Find solution for Sum = 0..Sum = Sum -1, Sum, i represents sum 
     * at each stage */ 
     for (j=0; j<= 2; j++) { 
      /* Go over each coin that is lesser than the sum at this stage 
      * i.e. sum = i */ 
      if (coin[j] <= i) { 
       if ((1 + min[(i - coin[j])]) <= min[i]) { 
        /* E.g. if coin has value 2, then for sum i = 5, we are 
        * looking at min[3] */ 
        min[i] = 1 + min[(i-coin[j])]; 
        printf("\nsetting min[%d] %d",i, min[i]); 
       } 
      } 
     } 
    } 
} 
void 
initializeMin() 
{ 
    int i =0; 
    for (i=0; i< 12; i++) { 
     min[i] = 100; 
    } 
} 
void 
dumpMin() 
{ 
    int i =0; 
    for (i=0; i< 12; i++) { 
     printf("\n Min[%d]: %d", i, min[i]); 
    } 
} 
int main() 
{ 
    initializeMin(); 
    findMin(11); 
    dumpMin(); 
} 

Answer 8

主なアイデアは、 - 各コインjについて、値[J] < = I（すなわち和）我々はi値[j]が見つかりコインの最小数を見て、和（Mましょう） （以前に発見された）。 m + 1が現在の合計iですでに見つかったコインの最小数よりも少ない場合、アレイ内のコインの数を更新します。 EXについて

- 後和= 11、N = 3と値[] = {1,3,5}
は、我々はI = 3和を観察できるように、我々は

i- 1 mins[i] - 1 
i- 2 mins[i] - 2 
i- 3 mins[i] - 3 
i- 3 mins[i] - 1 
i- 4 mins[i] - 2 
i- 5 mins[i] - 3 
i- 5 mins[i] - 1 
i- 6 mins[i] - 2 
i- 7 mins[i] - 3 
i- 8 mins[i] - 4 
i- 8 mins[i] - 2 
i- 9 mins[i] - 3 
i- 10 mins[i] - 4 
i- 10 mins[i] - 2 
i- 11 mins[i] - 3 

を取得し出力します5、8、10、我々は次の方法で私たちの前の最小値からすると改善 -

sum = 3, 3 (1+1+1) coins of 1 to one 3 value coin 
sum = 5, 3 (3+1+1) coins to one 5 value coin 
sum = 8, 4 (5+1+1+1) coins to 2 (5+3) coins 
sum = 10, 4 (5+3+1+1) coins to 2 (5+5) coins. 

だから、合計= 11のために、我々は3（5 + 5 + 1）として答えを得るでしょう。

ここではCのコードがあります。トップコードページにある擬似コードと似ていますが、これは上記の答えの1つで提供されています。

int findDPMinCoins(int value[], int num, int sum) 
{ 
    int mins[sum+1]; 
    int i,j; 

    for(i=1;i<=sum;i++) 
     mins[i] = INT_MAX; 

    mins[0] = 0; 
    for(i=1;i<=sum;i++) 
    { 
     for(j=0;j<num;j++) 
     { 
      if(value[j]<=i && ((mins[i-value[j]]+1) < mins[i])) 
      { 
       mins[i] = mins[i-value[j]] + 1; 
       printf("i- %d mins[i] - %d\n",i,mins[i]); 
      } 
     } 
    } 
    return mins[sum]; 
} 

Answer 9

int getMinCoins(int arr[],int sum,int index){ 

     int INFINITY=1000000; 
     if(sum==0) return 0; 
     else if(sum!=0 && index<0) return INFINITY; 

     if(arr[index]>sum) return getMinCoins(arr, sum, index-1); 

     return Math.min(getMinCoins(arr, sum, index-1), getMinCoins(arr, sum-arr[index], index-1)+1); 
    } 

は、i番目のコインを考えてみましょう。どちらかが含まれるかどうか。それが含まれている場合、値の合計はコインの値だけ減少し、使用されたコインの数は1だけ増加します。含まれていない場合、同様に残りのコインを探索する必要があります。私たちは最低でも2つのケースを取る。

Answer 10

これは古い質問ですが、これはJavaの解決策です。

import java.util.Arrays; 
import java.util.HashMap; 
import java.util.Map; 

public class MinCoinChange { 

    public static void min(int[] coins, int money) { 
     int[] dp = new int[money + 1]; 
     int[] parents = new int[money + 1]; 
     int[] usedCoin = new int[money + 1]; 
     Arrays.sort(coins); 
     Arrays.fill(dp, Integer.MAX_VALUE); 
     Arrays.fill(parents, -1); 

     dp[0] = 0; 
     for (int i = 1; i <= money; ++i) { 
      for (int j = 0; j < coins.length && i >= coins[j]; ++j) { 
       if (dp[i - coins[j]] + 1 < dp[i]) { 
        dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1); 
        parents[i] = i - coins[j]; 
        usedCoin[i] = coins[j]; 
       } 
      } 
     } 
     int parent = money; 
     Map<Integer, Integer> result = new HashMap<>(); 
     while (parent != 0) { 
      result.put(usedCoin[parent], result.getOrDefault(usedCoin[parent], 0) + 1); 
      parent = parents[parent]; 
     } 
     System.out.println(result); 
    } 

    public static void main(String[] args) { 
     int[] coins = { 1, 5, 10, 25 }; 
     min(coins, 30); 
    } 
}