Unbounded knapsack/coin change with optimal solution for non-standard coins

Question

I have the following problem:

Given a target size N and some denominations of some randomly generated coins stored in array denominations[] check using dynamic programming if there is an optimal solution which will fill the entire target with the least amount of coins used.

This is a typical example of coin change problem, however unlike real life currency where each denomination is carefully picked so that any target can be matched this is not the case.

I am familiar with the algorithm used in coin change problem and how to construct a dynamic programming array to find the solution but how do I check if there is a solution in the first place?

Answer 1

Let the state be denoted by DP[i][sum] :the minimum number of coins used to form sum using starting i coins of the array denominations . Then the recurrence can be formulated as:

DP[i][sum]= min(DP[i-1][sum],DP[i][sum-denominations[i]]+1)

Why?? The first DP[i-1][sum] denotes the number of coins needed to form sum using i-1 coins only (the case in which we exclude the i th denomination), The other case when we include the i th coin (Note : I have assumed we can include tthe coin multiple times that is why I wrote DP[i][sum-denominations[i]].

Now, The base cases, DP[i][0]=0 i.e. the NULL set(for all i belonging from 0 to n(the number of denominations)! and DP[0][i]=+INFINITY where 1<=i<=sum .

Now when the DP table is filled up, You can easily check whether DP[n(the size)][sum] is not equal to +INFINITY then there exists a solution else wise not..

If you know how to construct a solution (as you said) , You can construct the solution for this solution too..

P.S. : For allowing only single time inclusion of a coin denomination the recurrence changes to

DP[i][sum]= min(DP[i-1][sum],DP[i-1][sum-denominations[i]]+1)

by the same logic! I think base cases will be same!