Program crashes, Tree too large

Question

I'm trying to answer this problem as an exercise:

here are set of coins of {50,25,10,5,1} cents in a box.Write a program to find the number of ways a 1 dollar can be created by grouping the coins.

My solution involves making a tree with each edge having one of the values above. Each node would then hold a sum of the coins. I could then populate this tree and look for leaves that add 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 huge that after a few seconds the program crashes. I'm running this on a windows 7, quad core, with 8gb ram. A rough calculation tells me I should have enough memory.

Are my calculations incorrect? Does the OS limit how much memory I have access to? Can I fix it while still using this solution?

All feedback is appreciated. Thanks.

Edit1: I have verified that the above approach is wrong. By trying to build a tree with a set of only 1 coin. coins[] = {1};

I found that the algorithm still failed. After reading the post from Lenik and from João Menighin I came up with this solution that ties both Ideas together to make a recursive solution which takes any sized array

//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

I really do believe someone has to put the most efficient and simple possible implementation, it is an improvement on lenik's answer:
Memory: Constant
Running time: Considering 100 as n, then running time is about O(n (lg(n))) <-I am 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 this can be solved in constant time, because any sequence sum can be represented with a linear formula.

Answer 2

Problem might be infinite recursion. You are not incrementing c any where and loop runs with c<=100

Edit 1: I am not sure if

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

is actually taking it beyond 100. Please verify that

Edit 2: I missed the Sum being initialized correctly and it was corrected in the comments below.

Edit 3: Method to debug - One more thing that you can do to help is, Write a print function for this tree or rather print on each level as it progresses deeper in the existing code. Add a counter which terminates loop after say total 10 iterations. The prints would tell you if you are getting garbage values or your c is gradually increasing in a right direction.

Answer 3

Tree solution is totally wrong for this problem. It's like catching 10e6 tigers and then let go all of them but one, just because you need a single tiger. Very time and memory consuming -- 99.999% of your nodes are useless and should be ignored in the first place.

Here's another approach:

• notice your cannot make a dollar to contain more than two 50 cents
• notice again your cannot make a dollar to contain more than four 25 cent coins
• notice... (you get the idea?)

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's a combination!!
            }
        }
    }
}

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

ps. hope this solution is not too simple =)

Answer 4

There is a much easier 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[k-d[i]];
        }
    }
    cout << w[100] << endl;
    return 0;
}

(link to ideone)

The idea is to incrementally build the number of ways to make change by adding coins in progressively larger denomination. Each iteration of the outer loop goes through the results that we already have, and for each amount that can be constructed using the newly added coin adds the number of ways the combination that is smaller by the value of the current coin can be constructed. For example, if the current coin is 5 and the current amount is 7, the algorithm looks up the number of ways that 2 can be constructed, and adds it to the number of ways that 7 can be constructed. If the current coin is 25 and the current amount is 73, the algorithm looks up the number of ways to construct 48 (73-25) to the previously found number of ways to construct 73. In the end, the number in w[100] represents the number of ways to make one dollar (292 ways).

Answer 5

Ok, this is not a full answer but might help you. You can try perform (what i call) a sanity check. Put a static counter in TrieNode for every node created, and see how large it grows. If you did some calculations you should be able to tell if it goes to some insane values.

The system can limit the memory available, however it would be really bizarre. Usually the user/admin can set such limits for some purposes. This happens often in dedicated multi-user systems. Other thing could be having a 32bit app in 64bit windows environment. Then mem limit would be 4GB, however this would also be really strange. Any I don't think being limited by the OS is an issue here.

On a side note. I hope you do realize that you kinda defeated all object oriented programming concept with this code :).

Answer 6

I need more time to analyze your code, but for now I can tell that this is a classic Dynamic Programming problem. You may find some interesting texts here:

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

and here

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