Dynamic programming Optimal coin change

Question

I studied some problems with dynamic programming, and it was difficult for me to wrap my head around some code with regard to finding the fewest coins to make changes.

Let's say we have coins worth 25, 10 and 1, and we make changes to 30. Greed will return 25 and 5 (1), while the optimal solution will return 3 (10). Here is the code from the book on this issue:

def dpMakeChange(coinValueList,change,minCoins): for cents in range(change+1): coinCount = cents for j in [c for c in coinValueList if c <= cents]: if minCoins[cents-j] + 1 < coinCount: coinCount = minCoins[cents-j]+1 minCoins[cents] = coinCount return minCoins[change] 

If anyone can help me wrap my head around this code (line 4 is where I start to get confused), that would be great. Thanks!

Answer 1

It seems to me that the code solves the problem for each price value to the value of the target value. Given the target value of v and the set of coins C , you know that the optimal choice of coin S should be of the form union(S', c) , where C is some coin from C and S' is the optimal solution for v - value(c) (sorry my notation). Therefore, the problem is the optimal substructure . The dynamic programming approach is the solution to any possible subtask. It takes the steps cents * size(C) , unlike something that explodes much faster if you are just trying to translate a forced direct solution.

 def dpMakeChange(coinValueList,change,minCoins): # Solve the problem for each number of cents less than the target for cents in range(change+1): # At worst, it takes all pennies, so make that the base solution coinCount = cents # Try all coin values less than the current number of cents for j in [c for c in coinValueList if c <= cents]: # See if a solution to current number of cents minus the value # of the current coin, with one more coin added is the best # solution so far if minCoins[cents-j] + 1 < coinCount: coinCount = minCoins[cents-j]+1 # Memoize the solution for the current number of cents minCoins[cents] = coinCount # By the time we're here, we've built the solution to the overall problem, # so return it return minCoins[change] 

Answer 2

Here's a way to think about the problem of changing coins, which can be useful if you like graph theory.

Suppose you have a chart defined as follows:

• For each unit of money (for example, a penny), there is one node from 0 to the value you are interested in (for example, 39 cents or something else.)
• There is one arc between any two nodes separated exactly by the value of the coin that you can use (for example, a node between 34 cents and 29 cents if you are allowed to use nickel.)

Now you can think of the problem of changing coins as the shortest problem of the path from your interest value to zero, because the number of coins will be exactly the same as the number of arcs in your path.

The algorithm does not use the terminology of graph theory, but it does basically the same thing: the outer loop covers all the "cents" (or nodes within the graph theory), and the inner loop varies along all arcs (values ​​in coinValueList) from the current arc to the next arcs. Together, they seek the shortest path from zero to your value. (A value to zero, zero to a value, does not matter. Traditionally, we look down to zero.)

I just started to understand dynamic programming when I realized that many problems can be posed as problems with graphics. (Be careful though ... not all of them can. Some of them are hypergraphs, and some probably not even that, but that helped me a lot.)

Answer 3

I think the fourth line is confused, because although Python can select / filter in list comprehension (transform(x) for x in iterable if condition(x)) , it cannot do the same in its standard for x in iterable: expression for x in iterable:

So, one (cheesy by them) person goes around to cook together. They create a list comprehension that does not actually do any conversion (thus c for c in coinValueList ) so that they can add an if c <= cents clause. And then use this as iterable for the standard expression for x in iterable: I suspect what causes your confusion.

An alternative way to write this line is:

 ... for eachCoinValue in filter(lambda x: x <= cents, coinValueList): ... 

Or, even more clearly, using the “drop down target” will be:

 ... smallEnoughCoins = filter(lambda each: each <= cents) for each in smallEnoughCoins: ...