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

it do not work if the coin array dont have coin 1.

i.e. coin 1 is a must for this code to work.

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.

it’s not working properly