The minimum number of coins the sum of which is S

Question

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.

Solution 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.

Solution 2

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

Solution 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).

Solution 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.

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

View more solutions