Trying to solve the recurrence equation for this, but I am not sure how to begin
ID: 3742899 • Letter: T
Question
Trying to solve the recurrence equation for this, but I am not sure how to begin since the output of each is true/false.
This is a different variant of the coin changing problem. You are given denominations 1,r2,..,rn and you want to make change for a value B. You can use each denomination at most once and you can use at most k coins. Input: Positive integers x,....Xn. B,k Output: True/False, whether or not there is a subset of coins with value B where each denomination is used at most once and at most k coins are used. Design a dynamic programming algorithm for this problem. For simplicity, you can assume thatExplanation / Answer
Let isCoinSum(int coins[], int n, int B,int coin_count) be the function to find whether there is a coin chnage possible with coins[] to sum equal to B. n is the number of coins. coin_count is the number of coins currently .
The isCoinSum problem can be divided into two subproblems
a) Include the last coin, recur for n = n-1, B = B - coins[n-1]
b) Exclude the last coin, recur for n = n-1.
If any of the above the above subproblems return true, then return true.
Following is the recursive formula for isCoinSum() problem.
isCoinSum(coins, n, B ,coin_count) = isCoinSum(coins, n-1, B ,coin_count ) ||
isCoinSum(coins, n-1, B-coins[n-1],coin_count+1)
Base Cases:
isCoinSum(coins, n, B ,coin_count) = false, if (B > 0 and n == 0 ) or (coin_count>k).
isCoinSum(coins, n, B ,coin_count) = true, if B == 0 and coin_count <=k;