минимальное количество монет, сумма которых равна S

17

Дан список из N монет, их значений (V1, V2, ..., VN) и общей суммы S. Найдите минимальное количество монет, сумма которых равна S (мы можем использовать столько монет, сколько одного типа, как мы хотим), или сообщите, что невозможно выбрать монеты таким образом, чтобы они суммировались до S.

Я пытаюсь понять динамическое программирование, не понял этого. Я не понимаю данное объяснение, так что, может быть, вы можете дать мне несколько советов, как программировать эту задачу? Нет кода, только идеи, с которых я должен начать.

Спасибо.

    
задан good_evening 22.11.2010 в 17:25
источник
  • Может быть, статья с минимальными монетами здесь может помочь techieme.in/minimum-number-of-coins –  dharam 12.03.2015 в 18:48

11 ответов

6

Это классическая проблема с рюкзаком, посмотрите здесь дополнительную информацию: Проблема с рюкзаком из Википедии

Вам также следует взглянуть на некоторую сортировку, в частности, сортировку от наибольших к наименьшим значениям.

    
ответ дан kyndigs 22.11.2010 в 17:31
11

Точный ответ на эту проблему хорошо объяснен здесь. Ссылка

    
ответ дан satarasu 07.05.2011 в 04:10
3

Как уже указывалось, динамическое программирование лучше всего подходит для этой проблемы. Я написал программу на 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 является no. монет, необходимых для получения этой суммы. Ответ для ввода выше (получение значения 12) - 3 (монеты значений 5, 5, 2).

    
ответ дан Barun Sharma 13.04.2014 в 21:08
2

Я думаю, что вам нужен такой подход:

Вы знаете, что хотите произвести сумму S . Единственный способ произвести S - сначала произвести S-V1 , а затем добавить монету со значением V1 ; или произвести S-V2 , а затем добавить монету со значением V2 ; или ...

В свою очередь, T=S-V1 получается из T-V1 , или T-V2 , или ...

Делая шаг назад, вы можете определить наилучший способ, если он есть, получить S из вашего V s.     

ответ дан Chowlett 22.11.2010 в 17:36
  • Этот метод известен путано-общим термином «динамическое программирование». –  Phrogz 22.11.2010 в 17:37
  • Более конкретно, memoization при использовании в этом сверху вниз. –  joscarsson 07.12.2013 в 13:15
1

На вопрос уже дан ответ, но я хотел предоставить рабочий код 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(); 
}
    
ответ дан Gaurav Sinha 14.09.2014 в 07:18
0

Я не знаю о динамическом программировании, но я бы так и сделал. Начните с нуля и переходите к S . Создайте набор с одной монетой, затем с этим набором создайте набор из двух монет и так далее ... Найдите S и игнорируйте все значения, превышающие S . Для каждого значения запомните количество использованных монет.

    
ответ дан Dialecticus 22.11.2010 в 17:45
0

Многие люди уже ответили на вопрос. Вот код, который использует 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;
}
    
ответ дан Sergey 29.07.2013 в 06:05
  • Правильно ли я предполагаю, что возвращенный связанный список представляет собой список монет для составления требуемой суммы? Если это так, эта программа, похоже, не работает для набора {8, 7, 1} и суммы 14 (я получаю 8 и шесть 1сек). Если нет, что представляют цифры в списке coinsSet? –  JohnK 13.08.2013 в 00:46
  • Определение проблемы позволяет повторно использовать монеты («мы можем использовать столько монет одного типа, сколько хотим»). В списке представлены монеты, которые суммируются до заданной суммы. В вашем примере {8, 7, 1} -> Сумма ({8, 1, 1, 1, 1, 1, 1}) = 14 –  Sergey 14.05.2014 в 00:19
  • Sergey, Правильный ответ для множества {8, 7, 1} и сумма 14 - 2 монеты по 7 каждый (7 + 7 = 14). Ваш ответ 8 + 1 + 1 + 1 + 1 + 1 + 1 = 14 с использованием 7 монет неправильный. –  P L Patodia 29.07.2014 в 06:04
0

Основная идея заключается в том, что для каждой монеты j, значение [j] < = i (то есть сумма), мы смотрим на минимальное количество монет, найденных для i-value [j] (скажем, m) суммы (ранее найденной). ). Если m + 1 меньше минимального количества монет, уже найденных для текущей суммы i, то мы обновляем количество монет в массиве.

Для ex - sum = 11 n = 3 и value [] = {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 

Как мы можем наблюдать для суммы 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. Он похож на псевдокод, приведенный на странице 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];
}
    
ответ дан learner 29.03.2015 в 21:14
0
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. Если она не включена, то нам нужно исследовать оставшиеся монеты аналогичным образом. Мы берем минимум два случая.     

ответ дан Mostafizar 17.02.2017 в 23:06
0

Я знал, что это старый вопрос, но это решение в 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);
    }
}
    
ответ дан Bahador Biglari 14.12.2017 в 21:03
0

Для быстрого рекурсивного решения вы можете проверить эту ссылку: решение java

Я прохожу минимальные шаги, необходимые для поиска идеальной комбинации монет. Скажем, у нас есть coins = [20, 15, 7] и monetaryValue = 37 . Мое решение будет работать следующим образом:

[20] -> sum of array bigger than 37? NO -> add it to itself
[20, 20] greater than 37? YES (20 + 20) -> remove last and jump to smaller coin
[20, 15] 35 OK
[20, 15, 15] 50 NO
[20, 15, 7] 42 NO
// Replace biggest number and repeat
[15] 15 OK
[15, 15] 30 OK
[15, 15, 15] 45 NO
[15, 15, 7] 37! RETURN NUMBER!
    
ответ дан Lucio 19.07.2018 в 15:55