The Coin Problem – Dynamic Programming

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.

Example: Given coins with values 1, 3, and 5.
And the sum S is 11.
Output: 3, 2 coins of 3 and 1 coin of 5

This questions was asked in Amazon written test. This problem is also known as Knapsack problem.

Solution:

We will solve this problem using dynamic programming.
Dynamic programming is a top-down approach: split the larger problem into smaller ones, solve the smaller ones (putting away the solution for each smaller problem somewhere so that it can be used again in case needed later), and combine to produce the solution to the larger problem.

First of all we need to find a state for which an optimal solution is found and with the help of which we can find the optimal solution for the next state.

We will create an array Min[i] for minimal sets with sum = i. Min[0]=0.
We come through i=1 to S inclusive and check whether Min[i]>Min[Min[i-v]+1] for each v in a given array. If so, we set Min[i] to this value.

Implementation:

#include<stdio.h>
#include<stdlib.h>

int minCoins( int a[], int N, int S ){
/* N: Length of the array */

int *min = (int *)malloc(sizeof(int)*(S+1));
int i,j;
for(i=0;i<=S;i++)
	min[i]= INT_MAX; // start with extremly large value

min[0]=0;
for(i=1;i<=S;i++)
{
	for(j=0;j<N;j++)
	{
		if(i>=a[j])
		{
			if(min[i-a[j]]+1<min[i])
			min[i] = min[i-a[j]]+1;
		}
	}
}

if(min[S]== INT_MAX)
	return -1;

return min[S];
}

// main function to check above functionality
int main()
{
	int a[]={1,3,5};
	int size = sizeof(a)/sizeof(a[0]);
	int d = minCoins(a,size,11);
	printf("%d",d);
	return 0;
}

This procedure requires extra space proportional to the amount. This may not always be possible. However, this algorithm is linear in time.

Source: Top Coder

0 Thoughts on “The Coin Problem – Dynamic Programming

  1. Rahul Sharma on January 2, 2015 at 10:21 pm said:

    it do not work if the coin array dont have coin 1.
    i.e. coin 1 is a must for this code to work.

  2. Rahul Sharma on January 2, 2015 at 10:46 pm said:

    replace your INT-MAX with INT_MAX-2 and your code will be fine.
    Because in your current code INT_MAX+1 causes nasty stuff bec of circular int causes it to become negative value.

  3. anushka tivari on July 22, 2016 at 12:32 pm said:

    it’s not working properly

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Post Navigation