Program crash, tree too big

Question

I am trying to answer this problem as an exercise:

Here are coins from {50,25,10,5,1} cents in the box. Write a program to find the number of ways to create 1 dollar by grouping coins.

My solution involves creating a tree with each edge having one of the values ​​above. Each node will hold the amount of coins. I could then fill this tree and look for leaves that are up to 100. So here is my code

class TrieNode { public: TrieNode(TrieNode* Parent=NULL,int sum=0,TrieNode* FirstChild=NULL,int children=0, bool key =false ) :pParent(Parent),pChild(FirstChild),isKey(key),Sum(sum),NoChildren(children) { if(Sum==100) isKey=true; } void SetChildren(int children) { pChild = new TrieNode[children](); NoChildren=children; } ~TrieNode(void); //pointers TrieNode* pParent; TrieNode* pChild; int NoChildren; bool isKey; int Sum; }; void Populate(TrieNode* Root, int coins[],int size) { //Set children Root->SetChildren(size); //add children for(int i=0;i<size;i++) { TrieNode* child = &Root->pChild[0]; int c = Root->Sum+coins[i]; if(c<=100) { child = new TrieNode(Root,c); if(!child->isKey) //recursively populate if not a key Populate(child,coins,size); } else child = NULL; } } int getNumKeys(TrieNode* Root) { int keys=0; if(Root == NULL) return 0; //increment keys if this is a key if(Root->isKey) keys++; for(int i=0; i<Root->NoChildren;i++) { keys+= getNumKeys(&Root->pChild[i]); } return keys; } int _tmain(int argc, _TCHAR* argv[]) { TrieNode* RootNode = new TrieNode(NULL,0); int coins[] = {50,25,10,5,1}; int size = 5; Populate(RootNode,coins,size); int combos = getNumKeys(RootNode); printf("%i",combos); return 0; } 

The problem is that the tree is so large that after a few seconds the program crashes. I run this on windows 7, a quad core, with 8 GB of RAM. A rough calculation tells me that I should have enough memory.

Are my calculations wrong? Does the OS limit the amount of memory that I have access to? Can I fix this while still using this solution?

All reviews are welcome. Thanks.

Edit1: I confirmed that the above approach is incorrect. Trying to build a tree with a set of 1 coin. coins [] = {1};

I found that the algorithm still does not work. After reading a post from Lenik and from João Menigin, I came up with this solution that combines both ideas together to make a recursive solution that accepts any array size

 //N is the total the coins have to amount to int getComobs(int coins[], int size,int N) { //write base cases //if array empty | coin value is zero or N is zero if(size==0 || coins[0]==0 ||N==0) return 0; int thisCoin = coins[0]; int atMost = N / thisCoin ; //if only 1 coin denomination if(size==1) { //if all coins fit in N if(N%thisCoin==0) return 1; else return 0; } int combos =0; //write recursion for(int denomination =0; denomination<atMost;denomination++) { coins++;//reduce array ptr combos+= getComobs(coins, size-1,N-denomination*thisCoin); coins--;//increment array ptr } return combos; } 

Thanks for all the feedback.

Answer 1

The tree solution is completely wrong for this problem. It is like catching 10e6 tigers, and then letting go of all but one, just because you need one tiger. A lot of time and memory - 99.999% of your nodes are useless and should be ignored first.

Here's a different approach :

• Please note that your dollar cannot contain more than two 50 cents.
• note that your dollar cannot contain more than four coins in denominations of 25 cents.
• notice ... (do you understand?)

Then your solution is simple:

 for( int fifty=0; fifty<3; fifty++) { for( int quarters=0; quarters<5; quarters++) { for( int dimes=0; dimes<11; dimes++) { for( int nickels=0; nickels<21; nickels++) { int sum = fifty * 50 + quarters * 25 + dimes * 10 + nickels * 5; if( sum <= 100 ) counter++; // here a combination!! } } } } 

You may ask why I did not do anything with one cent coins? The answer is simple, as soon as sum less than 100, the rest are filled with 1 cents.

ps. hope this solution is not too easy =)

Answer 2

Well, this is not a complete answer, but it can help you. You can try to perform (what I call) a health check. Put a static counter in TrieNode for each node created and see how it grows. If you have done some calculations, you should be able to tell if these are some crazy values.

The system may limit the available memory, however it will be really strange. Usually, the user / administrator can set such restrictions for some purposes. This often happens in specialized multi-user systems. Another thing is to have a 32-bit application in a 64-bit Windows environment. Then the memory limit will be 4 GB, however it will also be really strange. Any, I don’t think OS limitation is the problem here.

On a side note. I hope you understand that you lost the whole concept of object-oriented programming with this code :).

Answer 3

I need more time to parse your code, but now I can say that this is a classic dynamic programming problem. Here you can find interesting texts:

http://www.algorithmist.com/index.php/Coin_Change

and here

http://www.ccs.neu.edu/home/jaa/CSG713.04F/Information/Handouts/dyn_prog.pdf

Answer 4

There is a much simpler way to find a solution:

 #include <iostream> #include <cstring> using namespace std; int main() { int w[101]; memset(w, 0, sizeof(w)); w[0] = 1; int d[] = {1, 5, 10, 25, 50}; for (int i = 0 ; i != 5 ; i++) { for (int k = d[i] ; k <= 100 ; k++) { w[k] += w[kd[i]]; } } cout << w[100] << endl; return 0; } 

( link to ideone )

The idea is to gradually increase the number of ways to make changes by adding coins in a larger denomination. Each iteration of the outer loop goes through the results that we already have, and for each amount that can be built using the recently added coin, the number of ways is added when a combination that is smaller than the current coin can be built. For example, if the current coin is 5 and the current amount is 7 , the algorithm looks for the number of ways 2 can be constructed, and adds it to the number of ways 7 can be built. If the current coin is 25 , and the current amount is 73 , the algorithm looks for the number of construction methods 48 ( 73-25 ) of the previously found number of construction methods 73 . In the end, the number in w[100] represents the number of ways to make one dollar (292 ways).

Answer 5

I really believe that someone should deliver the most efficient and easiest possible implementation, this is an improvement in response to lenik:
Memory: Permanent
Runtime: counting 100 as n , then the runtime is around O (n (log (n))) <-I uns unsure

 for(int fifty=0; fifty <= 100; fifty+=50) for(int quarters=0; quarters <= (100 - fifty); quarters+=25) for(int dimes=0; dimes <= (100 - fifty - quarters); dimes+=10) counter += 1 + (100 - fifty - quarters - dimes)/5; 

I think that this can be solved in a constant time, because any sum of the sequence can be represented by a linear formula.

Answer 6

The problem can be infinite recursion. You do not increment c anywhere, and the loop works with c <= 100

Edit 1: I'm not sure

 int c = Root->Sum+coins[i]; 

actually takes it beyond 100. Please make sure

Edit 2: I missed the correct initialization of the amount, and it was fixed in the comments below.

Edit 3: Debugging Method - Another thing you can do to help is write a print function for this tree, or rather print at each level as it moves deeper into existing code. Add a counter that completes the loop after it says a total of 10 iterations. The fingerprints will tell you if you get garbage values, or your c is gradually increasing in the right direction.