Минимальное количество монет, сумма которых равна 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. Произведите набор с одной монетой, затем с этим набором создайте набор из двух монет и так далее ... Найдите 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 для этого: -

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) 

Для ввода:

12 2 3 5

Выход будет:

[0, -1, 1, 1, 2, 1, 2, 2, 2, 3, 2, 3, 3] 3 list_index является общей необходимости и значение в list_index - нет. монет, необходимых для получения этой суммы. Ответ для вышеуказанного ввода (получение значения 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] (скажем м) сумма (ранее найдено). Если m + 1 меньше минимального количества монет, уже найденных для текущей суммы i, то мы обновляем количество монет в массиве.

Для экс - сумма = 11 п = 3 и значение [] = {1,3,5}
Ниже на выходе мы получаем

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 

Как мы можем наблюдать за сумму я = 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. Его аналогично псевдокоду, указанному на странице topcoder, ссылка на которую приведена в одном из приведенных выше ответов.

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); 
    } 

Рассмотрим я-ю монету. Либо он будет включен, либо нет. Если он включен, то сумма значения уменьшается на величину монеты, а количество используемых монет увеличивается на 1. Если оно не включено, нам нужно исследовать оставшиеся монеты аналогично. Мы берем минимум два случая.

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); 
    } 
}