Dynamic Programming: Combination Sum Problem

Tuesday Aug 12th 2008 by Nirav Bhatt
Share:

Find the coin combinations that add up to a dollar.

In this article, I present an alternative solution to a well-known "how many coins form a dollar" problem. The approach takes dynamic programming into use, which is known to solve problems of changing states. Typical problems of dynamic programming include fibonacci and factorials—the ones that involve recursion as their first choice of techniques.

Problem Statement

Find out all combinations of coins 1, 5, 25, and 50 cents that form a dollar. A popular version of this problem also involves a dime (10 cents). This article tries to emphasize the concept involved: the role of Dynamic Programming. At the end, it is easy to see that solution is extendable to any number of coins that form a desired sum.

In mathematical jargon, you have N coins with values V1, V2, ..., VN and you need to obtain all the combinations that form your desired sum S with the help of one or more of these coins, combined or one at a time.

Manual Approach

In the case of the dollar problem, it is not impossible to figure out the solution manually. With pen and paper, you can start deriving it like this:

  1. How many ways 1s, 5s, 25s, or 50s can form a 100, taken one at a time: You need 100 1s, 20 5s, 4 25s, or 2 50s.
  2. How many ways 1s and 5s can form a 100: You need to try from 1 to 19 5s and figure out how many 1s would be required to make the rest to get a hundred.
  3. Similarly, how many ways 5s and 25s, 25s and 50s, 1s and 25s, 1s and 50s, can form 100.
  4. The number of ways how 100 can be obtained from three coins. From Steps 2 and 3 above, you know all the double coin combinations that form a 100. For example, put all 1s and 5s that form a 100 on one side. Now, make them form a 75, instead of 100. As you guessed it, simply append a 25. and you got one combination.

Make them form a 50, append 2 25s, and you have the second three-coin combination, and so on. To understand, look at these calculations:

1 5 95 1       = 100
2 5 90 1       = 100
... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...
19 5 5 1       = 100
... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...
1 5 14 5 = 75 + 1 25 = 100
1 5 9 5 = 50 + 2 25 = 100

Once you have all the ways that three coins can form a sum, it is not hard to repeat the same process for the forth coin. Simply repeat what you did in Step 4 above, with three-coin combinations already arrived at to begin with, and append the fourth coin to every combination.

You begin getting tired after writing it all, but with careful and repetitive efforts, the correct solution can be arrived at, although I do not recommend it. The reason? Simply adding one more coin VN+1 (a dime that I purposefully omitted!) to the problem will make it an Olympic-sized task. Dynamic programming is here to solve exactly this type of problem. Although you are only demonstrating the approach with four coin values, you will see that attempting it with a considerably larger number of coins does not make it extremely complex. Also, the algorithm is much more efficient with higher coin values compared to the brute force approach, which you will also examine at the end.

The DP Approach: A Formula?

Dynamic Programming tries to identify states and the conditions that change them. All you need is a function that relates an integer n with n - 1 (or its nearest relative, depending on the nature of problem).

A famous example of a DP solution is factorial, where through recursion you arrive at the solution one number at a time.

In case of factorial, the function is:

F (n) = n*f (n - 1) if n>1
= 1 If n = 1

Try to get something like this for your problem. The coin problem requires you to get a sum S from V1, V2, ..., VN coins. You can define it as this:

S = aV1 + bV2 + cV3 + ... + kVN

You need to find a, b, c,...,k and present them along with V1, V2,...,VN as a combination solution.

State Identification and Transition

Because you want to proceed step-by-step in DP, and the manual approach stated earlier already gives you some hints, try to build from the ground up. You always can arrive at a given sum from two values (coins). The algorithm goes something like this:

For i = 1 to Sum / V1
For j = 1 to Sum / V2

total = i* V1 + j* V2;

If (total == Sum)
   return i V1   j V2;
else
   continue;

Above is actually the essence of the brute-force approach (described at the end), but your final solution isn't, as you will know soon. You have, in your code, optimized the algorithm above to loop only for (Sum - V2) / V1 and (Sum - V1) / V2, respectively, to reduce looping. This is because when you consider a Sum S with two components V1 and V2, V1 should be repeated so that at least one V2 can be added to form S, and vice versa for V2. (If it is not clear, try putting 5 and 25 for V1 and V2, for S = 100).

Do not forget that you are attempting combinations of exactly two coins that form a sum—a combination of a single type of coin is separately arrived at, and isn't really a rocket science thing. A hundred can be formed using 100 1s, 2 50s, 4 25s, or 20 5s, and even a child can tell you that this can be done by simple division. That's why you have taken two numbers as the building block of your algorithm, and not one.

The corrected, optimized, algorithm now is:

For i = 1 to (Sum - V2 ) / V1
For j = 1 to (Sum - V1 ) / V2

total = i* V1 + j* V2;

If (total == Sum)
   return i V1  j V2;
else
   continue;

You have accomplished the first step: obtaining all combinations of two coins that form a sum S. In code, the Comb2() function corresponds to this functionality, which takes two int parameters a and b, and yields all combinations of them that total up to sum S. As a return value, I have chosen the type vector<map <int> >, because you expect a number of combinations, each having two (or more) coin values (keys of map) V1 and V2, and their respective required numbers (values of the map).

A partial output of the Comb2() function with coin values a=5, b=25 to obtain sum = 100:

Output Vector Vect: contains Vect1, Vect2....VectN

Vect1: 5 : 5  25 : 3 --- 5 coins of 5 cents, 3 coins of 25 cents.

Vect2: 5 : 10  25 : 2 --- 10 coins of 5 cents, 2 coins of 25 cents.
Note: The order in actual output may differ; this is only for illustration. Also, this only shows two elements of the resultant vector.

Now, look at the three-coin combinations that total 100; all three are required in every combination. Take as an example 1 cent, 5 cent, and 25 cent coins to form a dollar. You already have a method to obtain any sum from coins 1 and 5. The other coin remaining is 25. Your target sum is 100.

So, change your target sum to 100 - 25 = 75. Try obtaining combinations of 1 and 5 for sum 75. Comb2() will give you the vector of vectors. Once you have it, append exactly one 25 to every combination, and you have a 100!

Next, change your target sum to 100 - 2*25 = 50. Try obtaining combinations of 1 and 5 for sum 50. Comb2() will again give you a vector of vectors. Once you have it, append exactly two 25s to every combination, and again you have a 100!

There is room for one more 25. So, repeat the process above by multiplying 25 by 3, try to obtain combinations for sum 25, and you are done with this one.

Just as you excluded 25 above, you just need to repeat this process, once for 5, and once 1, to arrive at all the combinations.

After you have all the combinations, you can repeat the above process taking 5, 25 and 50; 25, 50, 1; and 50, 1, 5.

This is what exactly the Comb3() function does. It takes three int parameters—a, b, and c—and yields all combinations of them that total up to sum S. As with Comb2(), it again returns vector of maps, with keys as coin values V1, V2, V3... and values as their required number a, b, c....

This can propagate to more levels. Comb4() takes it to the sum of four different coin values, with the buildup already done by Comb3(), and so on. This can be generalized to use recursion (just like factorials), but for the puzzle's sake, I have limited myself to four coin combinations.

Finally, take a look at the Brute Force approach, which is infinitely extensible to contain any number of coins, but incurs high processor activity and memory usage due to excessive looping.

The Brute Force Approach

This takes all coins, one at a time, and puts them into nested For loops to arrive at combinations that form the given sum:

For i = 1 to Sum / V1
For j = 1 to Sum / V2
... ... ... ... ... ... ... ...
... ... ... ... ... ... ... ...
For r = 1 to Sum / VN

total = i* V1 + j* V2;

If (total == Sum)
   return i V1   j V2 ... r VN;
else
   continue;

As you can see, it tries to match everything with everything, and no optimizations are performed.

As a means of comparison to the DP approach, I have included a BruteForceTest() function in the code; it also will take three parameters corresponding to three coin values, and yield combinations that total up to a desired sum S.

The .exe is a console application that displays all combinations with both the approaches. Conditionally, one also can log the results to a file by uncommenting a #define DO_LOG line. The code displays the time taken by both the approaches, and also logs them if logging is enabled. The logging for both approaches happens to two different files for easy comparison.

In my test runs, BruteForceTest() takes around 15+ ms on a Windows XP workstation as well as a Windows 2003 Server. The DP approach completes in almost 0 ms. Repetitive runs reduce the BruteForceTest() running time to 0 ms, but this is due to binary code being cached. With a higher number of coins, the DP approach can definitely add substantial performance gains.

I would like to hear from all because this is my first CodeGuru submission. Your comments and suggestions are welcome for the article as well as the code.

Share:
Home
Mobile Site | Full Site
Copyright 2017 © QuinStreet Inc. All Rights Reserved