Dynamic Programming: Combination Sum Problem

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.



About the Author

Nirav Bhatt

A VC++ vetaran. Currently Working in GUI team of a world class Enterprise Product company's India office.

Downloads

Comments

  • uno de los estilos GHD están en descuento

    Posted by swvlcy317 on 07/17/2013 11:06pm

    Aarhus que aman la cultura, los artículos de moda todo el tiempo, que están dispuestos a ser generosos temperament.They también tienen este problema, salir a nadar o esquiar etc proyecto de espectáculos inevitablemente perturbar el pelo original, lo que resulta en yourself.So muy embarazoso desea que un amigo, ya que pueden mantener los moment.Clothes perfectos y zapatos todo puede cambiar en cualquier pelo time.But? Aquí hemos introducido ghd glattejern.Resort son el must-have item.It no sólo es pequeña, de moda, conveniente para el voltaje de los países, el tiempo caliente es korte.som hasta diez minutos, que es el mismo que otro. [url=http://planchaspeloghd.cabanova.com/]planchas ghd baratas[/url] Web oficial de GHD es un servicio gratuito para comprobar la autenticidad del sitio, y usted tiene la intención de comprar su cuerpo de hierro (que recomiendo), el peso también GHD es mucho más bajo que otro hierro (preferiblemente GHD súper fácil que cualquier otra tabla), incluso junta con cable en forma de L de la auténtica GHD pseudoartrosis diferente L, por no hablar de los accesorios de embalaje tales como bolsos calientes pinzas ghd baratas ... que son fáciles de entender que los accesorios adecuados acompañar a su original de GHD es una copia descarada! Por último, para asegurarse de que su proveedor es oficial. [url=http://ghdplanchasprec.ucoz.com/]ghd baratas[/url] Pero el pelo no es lo mismo si se cuidan de él, así como algunos pelos. Una pequeña variación, que ir a la peluquería, pero también toma mucho tiempo para esperar. Para empezar a citas de pelo. Es una pérdida de tiempo posible. A veces el pelo no está haciendo lo que quiere. Aquí presentamos un producto ghd, es un buen producto de cuidado del cabello, aspecto elegante, colores nobles, operación simple, en cualquier momento para cambiar su peinado. Derecha caliente cerámica, el pelo no traerá ningún daño, sino que también ayuda a embellecer el cabello. Aquí en Dinamarca vendemos planchas ghd es el más barato, garantía de ser genuino ghd. Asegúrese de utilizar la vida y la seguridad de la propiedad.

    Reply
  • købe billige sort GHD glattejern,nye ghd IV sort

    Posted by carpinteyrohvg on 06/14/2013 11:34pm

    [url=http://ghdfladjerntilbud.webstarts.com/]GHD fladjern tilbud[/url] GHD Limited Lyserød er altid viser en stor stigning tendens til i denne sæson pink er en af tendensen i denne sæson. Den er udstyret med avancerede funktioner, såsom forbedret temperaturkontrol at bevare varme under styling, en dvaletilstand, og universelle spænding. Hertil kommer, GHD den perfekte styling af New Smukke Pink Styler Box sæt er en hemmelighed, forårsager alt er indkapslet i en smuk æske, hvilket gør dette sæt en perfekt gave!Du kan nyde gratis forsendelse til Danmark, ingen skat og spare op 50% off. Hvis du har andre spørgsmål, så kontakt os. vi har evnen til at levere dig den bedste service. Tøv ikke med, gribe chancen for at købe mode ghd fladjern.ghd glattejern er det absolut ypperste indenfor hårstyling. Med et ghd glattejern, kan du nemlig ikke bare glatte dit hår – du kan også bruge dit ghd glattejern til at skabe store, voluminøse glamourkrøller, bevægelse i længderne, svej i nakken eller masser af volume på toppen. [url=http://glattejernghd.bloguedobebe.com/]Glattejern ghd[/url] Ligesom enhver anden hårudglatningsmiddel i ghd hår stabil, den metalliske Collection glattejern garanteret sikker at bruge. De er drevet ved hjælp universel spænding, hvilket gør dem praktisk for styling farten. De metalliske serien stylers også komme med en varme-bevis sag og en to-årig garantiperiode.Den Metallic Collection indeholder tre ghd glattejern med et slankt og skinnende finish. De er nemlig: ghd skinnende Silver Metallic Series Styler, ghd Rich Ruby Red Metallic Series Styler, og ghd Sahara Gold Metallic Series Styler.Hver ghd glattejern i Metallic Collection har de samme innovative funktioner som den klassiske ghd guld V glattejern, en af de bedst sælgende stylers i ghd produktlinje. Disse stylers er velegnede til alle hårtyper. Også med deres keramisk varmelegeme teknologi designet til at forsegle fugt i individuelle hår tråde, er disse stylers alle garanteret til at give ekstra glans og glans til håret, hvad enten det er krøllet, vinkede eller stryges lige. [url=http://glattejernghdpris.webgarden.es/]Glattejern ghd pris[/url] Nu er jeg overvejer at købe en, fordi selvom jeg BABYLISS er fair, så vil jeg gøre mig føle sig afslappet, ikke spilde for meget tid og bølge hår, jeg ønsker at købe guld klassiker, dette er mit hår barber shop, i Her kan du finde, hvis du vil have en begrænset udgave af kassen er omkring 199 €, men de er online, kan du finde ganske billige … Bemærk dog være forsigtig, fordi der er en masse af efterligning, kan du sælge en Den falske priser væksthormonmangel.

    Reply
  • Optimized brute force method

    Posted by bkirunge on 07/21/2009 05:58am

    Below code will significantly reduce number of iterations in BruteForceMethod.

    for (w=0; w<=S/d; w++) {
    for (x=0; x<=(S-w*d)/c; x++) {
    for (y=0; y<=(S-(w*d+x*c))/b; y++) {
    for (z=0; z<=(S-(w*d+x*c+y*b))/a; z++) {
    int val= w*d + x*c + y*b + z*a;
    if (val == 100) {
    map temp;
    temp[a] = z;
    temp[b] = y;
    temp[c] = x;
    temp[d] = w;
    retVect.push_back(temp);
    }
    }
    }
    }
    }

    Reply
  • recursive version

    Posted by mendi80 on 02/05/2009 07:23pm

    #include
    #include
    
    int ways_num(int,int[],int);
    
    void main()
    {
    	int Nums[]={1,5,20};
    	int sum=20;
    	int size=sizeof(Nums)/sizeof(int);
    	int numofways = ways_num(sum,Nums,size); //algorithm
    	printf("N=%d\n", numofways);
    	getchar();
    }
    
    int ways_num(int s, int arr[],int arrsize)
    {
    	if (s<0)
    		return 0;
    	else if	(s==0 || arrsize==1)
    		return 1;
    	else
    		return ways_num(s,arr,arrsize-1)+ways_num(s-arr[arrsize-1],arr,arrsize);
    }

    Reply
Leave a Comment
  • Your email address will not be published. All fields are required.

Top White Papers and Webcasts

  • Managing your company's financials is the backbone of your business and is vital to the long-term health and viability of your company. To continue applying the necessary financial rigor to support rapid growth, the accounting department needs the right tools to most efficiently do their job. Read this white paper to understand the 10 essentials of a complete financial management system and how the right solution can help you keep up with the rapidly changing business world.

  • With 81% of employees using their phones at work, companies have stopped asking: "Is corporate data leaking from personal devices?" and started asking: "How do we effectively prevent corporate data from leaking from personal devices?" The answer has not been simple. ZixOne raises the bar on BYOD security by not allowing email data to reside on the device. In addition, Zix allows employees to maintain complete control of their personal device, therefore satisfying privacy demands of valued employees and the …

Most Popular Programming Stories

More for Developers

Latest Developer Headlines

RSS Feeds