Coin change(standard dp )

general
1

Given an unlimited supply of coins of denominations x1,x2…,we wish to make change for a value v using not more than k coins…
Please tell me the solution…

**EDIT:**I need to know the number of ways to do so…

EDIT2:
6.19. Here is yet another variation on the change-making problem (Exercise 6.17).
Given an unlimited supply of coins of denominations x1; x2; : : : ; xn, we wish to make change for
a value v using at most k coins; that is, we wish to find a set of k coins whose total value is v.
This might not be possible: for instance, if the denominations are 5 and 10 and k = 6, then we
can make change for 55 but not for 65. Give an efcient dynamic-programming algorithm for the
following problem.
Input: x1; : : : ; xn; k; v.
Question: Is it possible to make change for v using at most k coins, of denominations
x1; : : : ; xn?

2

What to you want as an answer?

Number of ways?

1 Like
3

Yes sorry I forgot to mention it

4

Is this something similar to Knapsack problem? Can you post the exact problem statement along with the sample cases(if given)?

5

Morover I think if it asks whether it is possible to construct a change with the given denominations, I can define DP[i][j] as the minimum number of coins needed to make j using i coins only…
Now I can check dp[n][sum] if it is less than k then I can make it elsewise not!
Correct me If I am wrong…

(I think this is a better solution for this problem as I guess my actual question will need 3 parameters(with a higher complexity).

6

Please See update 2… for Example 6.17(Coin Change) is

7

It’s the Coin Change problem.

8

Like in coin change, let dp[n][k] denote number of ways to make n using k coins and m be the total number of coins available. Then:

for i in 1,m and a[i]<=n:

dp[n][k]=dp[n-a[i]][k-1]

Base case dp[0][0]=1

But this approach consider 1+2 and 2+1 different, so for dictinct combinations, it is better to keep on adding only smaller elements further.

This approach is O(nkm).

9

You can use Dynamic Programming and achieve a O(nV).

Let C(j) = Number of coins needed to make change for j.
You can have the recurrence relation:
C(j) = [1 + min C(j-xi) ] V FALSE for all xi<=j

Base case : C(0) = 0 as you’d need 0 coins to obtain a value of 0.

So here C(1) = [1+ min C(1-xi)] V FALSE = FALSE. (as 1>xi)

similarly C(2) = C(3) = C(4) = FALSE

Now C(5) = 1+ min C(5-5) = 1+min C(0) = 1

.

C(10) = 1 too

.

C(15) = 1 + min {C(10),C(5)} = 1+ min{1,1} = 2.

Although, I think calculating C(z) where z isn’t a multiple of 5, is a waste. (eg: v = 12)
i.e. calculating C(z) where z isnt a multiple of the HCF of all xi, is a waste.

If a value isnt a multiple of the HCF of xi, then change for it cannot be obtained. This makes us form a O(v) table with just (v/HCF) entries. In this case, C(0), C(5),… This reduces the space utilised.

10

Can anyone please share some links for Coin Change problem ? I am actually working on it and have solved DBOY but want to have a solid grip .

11

Minimum coin change: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1247