The minimum number of coins the sum of which is S

问题:

Given a list of N coins, their values (V1, V2, ... , VN), and the total sum S. Find the minimum number of coins the sum of which is S (we can use as many coins of one type as we want), or report that it's not possible to select coins in such a way that they sum up to S.

I try to understand dynamic programming, haven't figured it out. I don't understand the given explanation, so maybe you can throw me a few hints how to program this task? No code, just ideas where I should start.

Thanks.

回答1:

This is a classic Knapsack problem, take a look here for some more information: Wikipedia Knapsack Problem

You should also look at some sorting, specifically sorting from Largest to Smallest values.

回答2:

The precise answer to this problem is well explained here. http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=dynProg

回答3:

As already pointed out, Dynamic Programming suits best for this problem. I have written a Python program for this:-

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)

For input:

12 2 3 5

The output would be:

[0, -1, 1, 1, 2, 1, 2, 2, 2, 3, 2, 3, 3] 3 The list_index is the total needed and the value at list_index is the no. of coins needed to get that total. The answer for above input(getting a value 12) is 3 ( coins of values 5, 5, 2).

回答4:

I think the approach you want is like this:

You know that you want to produce a sum S. The only ways to produce S are to first produce S-V1, and then add a coin of value V1; or to produce S-V2 and then add a coin of value V2; or...

In turn, T=S-V1 is producible from T-V1, or T-V2, or...

By stepping back in this way, you can determine the best way, if any, to produce S from your Vs.

回答5:

Question is already answered but I wanted to provide working C code that I wrote, if it helps anyone. enter code here

Code has hard coded input, but it is just to keep it simple. Final solution is the array min containing the number of coins needed for each sum.

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

回答6:

I don't know about dynamic programming but this is how I would do it. Start from zero and work your way to S. Produce a set with one coin, then with that set produce a two-coin set, and so on... Search for S, and ignore all values greater than S. For each value remember the number of coins used.

回答7:

Lots of people already answered the question. Here is a code that uses 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;
}

回答8:

The main idea is - for each coin j, value[j] <= i (i.e sum) we look at the minimum number of coins found for i-value[j] (let say m) sum (previously found). If m+1 is less than the minimum number of coins already found for current sum i then we update the number of coins in the array.

For ex - sum = 11 n=3 and value[] = {1,3,5}
Following is the output we get

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 

As we can observe for sum i = 3, 5, 8 and 10 we improve upon from our previous minimum in following ways -

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.  

So for sum=11 we will get answer as 3(5+5+1).

Here is the code in C. Its similar to pseudocode given in topcoder page whose reference is provided in one of the answers above.

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

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

Consider i-th coin. Either it will be included or not. If it is included, then the value sum is decreased by the coin value and the number of used coins increases by 1. If it is not included, then we need to explore the remaining coins similarly. We take the minimum of two cases.

回答10:

I knew this is a old question, but this is a solution in 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);
    }
}

回答11:

For a fast recursive solution, you can check this link: java solution

I am going through the minimum steps required to find the perfect coin combination. Say we have coins = [20, 15, 7] and monetaryValue = 37. My solution will work as follow:

[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!