4. You have a set of coins. Each coin i has value vi . Your goal is to find a se

Question

4. You have a set of coins. Each coin i has value vi . Your goal is to find a set of coins with total value exactly equal to V . You can use only one copy of each coin. Design a dynamic programming algorithm to determine whether it is possible to accomplish this. You don’t need to output which coins are used, just whether it is possible or not. Hint: this is similar to, but not the same as, the knapsack problem without item repetition. Like we did in the edit distance problem and the knapsack without repetition problem, you will need a 2-dimensional DAG. Define P(i, W) = True if you can get value W using coins 1, ..., i. How do you calculate P(i, W) using subproblems?

Treat single arithmetic operations (addition, subtraction, multiplication, and division) as constant time operations.

Explanation / Answer

DYNAMIC PROBLEM OF COIN:-

Here i have taken an example and written the program i.e

Given coins with values 1,3,5.and the sum is 11.

#include<stdio.h>

#include<stdlib.h>

int minCoins( int a[], int N, int S )

{

int *min = (int *)malloc(sizeof(int)*(S+1));

int i,j;

for(i=0;i<=S;i++)

                   min[i]= INT_MAX;

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

}

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;

}

Related Questions

Navigate

• Browse (All)
• Browse 4
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.