c++ - 程序崩溃，树太大

Question

我试图将这个问题作为练习来回答:

这里有一组装在盒子里的 {50,25,10,5,1} 美分的硬币。编写一个程序，找出通过将硬币分组来创造 1 美元的方法的数量。

我的解决方案涉及制作一棵树，每条边都具有上述值之一。然后每个节点将持有一定数量的硬币。然后我可以填充这棵树并寻找加起来为 100 的叶子。所以这是我的代码

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;
}

问题是这棵树太大了，几秒钟后程序就崩溃了。我在 windows 7，四核，8gb ram 上运行它。粗略计算一下，我应该有足够的内存。

我的计算有误吗？操作系统是否限制我可以访问的内存量？我可以在仍然使用此解决方案的同时修复它吗？

感谢所有反馈。谢谢。

编辑1:我已经验证了上面的做法是错误的。通过尝试用一组只有 1 个硬币来 build 一棵树。 硬币[] = {1};

我发现算法还是失败了。阅读 Lenik 和 João Menighin 的帖子后我想出了这个解决方案，将两个想法联系在一起以制作递归解决方案它接受任何大小的数组

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

感谢大家的反馈

Answer 1

对于这个问题，树的解决方案是完全错误的。这就像抓到 10e6 只老虎，然后只放一只老虎，只因为你需要一只老虎。非常耗费时间和内存——99.999% 的节点是无用的，应该首先忽略。

这是另一种方法:

• 注意你不能让一美元包含超过两个 50 美分
• 再次注意你不能让一美元包含超过四个 25 美分的硬币
• 注意...(你明白了吗？)

那么你的解决方案很简单:

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!!
            }
        }
    }
}

你可能会问，为什么我对一分币没有做任何事情？答案很简单，只要sum小于100，剩下的补1分。

附言。希望这个解决方案不是太简单 =)