7

I've been reviewing some dynamic programming problems, and I have had hard time wrapping my head around some code in regards to finding the smallest number of coins to make change.

Say we have coins worth 25, 10, and 1, and we are making change for 30. Greedy would return 25 and 5(1) while the optimal solution would return 3(10). Here is the code from the book on this problem: 

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 could help me wrap my head around this code (line 4 is where I start to get confused), that would be great. Thanks!

Improve this question
3
  • 1
    What is minCoins? Anyway, trying to solve this in general is equivalent to the knapsack problem(or maybe even worse), so finding the optimal solution in any case gets troublesome really fast. The solution probably depends on the coins you can use. Commented Dec 6, 2012 at 20:25
  • Writing for variable in [l for l in list_comprehension] is subjectively bad, only because I haven't seen it much... Commented Dec 7, 2012 at 1:48
  • 1
    It's awkward, but not really so horrible. It's just narrowing the list down. The same thing could have been accomplished with an if and a continue on the next line, but whatevs. Commented Dec 7, 2012 at 1:53

3 Answers 3

Reset to default
5

It looks to me like the code is solving the problem for every cent value up until target cent value. Given a target value v and a set of coins C, you know that the optimal coin selection S has to be of the form union(S', c), where c is some coin from C and S' is the optimal solution for v - value(c) (excuse my notation). So the problem has optimal substructure. The dynamic programming approach is to solve every possible subproblem. It takes cents * size(C) steps, as opposed to something that blows up much more quickly if you just try to brute force the 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]
Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

Nice and clear. Basically, we know that the collection of coins used to make change must consist of (a) some coin in coinValueList plus (b) a bunch of other coins used to make up the rest. So, "guess" a coin for (a), and look up the best way to make change on the rest. (Conveniently, the rest is smaller than change, so we must have found an optimal solution for it in an earlier loop iteration.) If we repeat this for every possible guess for (a) (i.e. every different coin value), then (at least) one of these (a)s plus its corresponding (b) must be optimal.
Thank you! This was very simple and well explained, and I now understand how this problem works.
@acjohnson55 Why it show it error when i call it like this dpMakeChange([1,7,10] , 23 , 7) It should return me 3 7's and and 2 1's
@ActingAngel I matched the method signature provided by @tect in the original question. minCoins is a preallocated array of size change + 1. Its preexisting contents don't matter, if you trace through the code. It should probably not be a parameter at all, so I understand your confusion.
4

Here is a way to think about the coin changing problem that may be useful, if you are comfortable with graph theory.

Assume you have a graph defined in the following way:

  • There is one node for every unit of money (e.g., pennies) from 0 up to the value you are interested in (e.g., 39 cents, or whatever.)
  • There is one arc between any two nodes separated by exactly the value of a coin you are allowed to use (e.g., a node between 34 cents and 29 cents if you are allowed to use nickels.)

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

The algorithm doesn't use a graph theory terminology, but it is doing basically the same thing: The outer loop is ranging over all the "cents" (or nodes, in the graph theory framework) and the inner loop is ranging over all the arcs (the values in coinValueList) from the present arc to the next arc. All together, they are looking for the shortest path from zero up to your value of interest. (Value down to zero, zero up to value, doesn't matter. Traditionally we search downward to zero, though.)

I only really started to understand dynamic programming when I realized many problems could be cast as graph problems. (Be careful, though-- not all of them can. Some are hypergraphs, and some are probably not even that. But it helped me a lot.)

Improve this answer

Comments

3

I think the fourth line is confusing because while Python can select/filter in a list comprehension (transform(x) for x in iterable if condition(x)), it can't do the same in its standard for x in iterable: expression.

So one (cheesy imo) way people get around that is to weld the two together. They create a list comprehension which actually does no tranformation (thus the c for c in coinValueList) just so they can add the if c <= cents clause on. And then use that as the iterable for a standard for x in iterable: expression. I suspect that's where some of your confusion is coming from.

An alternate way to have written that line might have been:

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

Or even more clearly, with an "intention revealing variable" would be:

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

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.