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 内存上运行它。粗略的计算告诉我我应该有足够的内存。

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

感谢所有反馈。谢谢。

Edit1： 我已经验证上述方法是错误的。通过尝试用一组只有 1 个硬币构建一棵树。硬币[] = {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;
}

感谢所有的反馈

score 3 · Accepted Answer

对于这个问题，树解决方案是完全错误的。这就像抓到 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 美分。

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

score 2 · Accepted Answer

好的，这不是一个完整的答案，但可能会对您有所帮助。您可以尝试执行（我所说的）健全性检查。为每个创建的节点放置一个static计数器TrieNode，看看它增长了多大。如果您进行了一些计算，您应该能够判断它是否达到了一些疯狂的值。

系统可以限制可用的内存，但这真的很奇怪。通常，用户/管理员可以出于某些目的设置此类限制。这经常发生在专用的多用户系统中。另一件事可能是在 64 位 Windows 环境中拥有 32 位应用程序。那么内存限制将是 4GB，但这也很奇怪。任何我认为不受操作系统限制的都是这里的问题。

在旁注中。我希望你确实意识到你用这段代码打败了所有面向对象的编程概念:)。

score 1 · Accepted Answer

我需要更多时间来分析您的代码，但现在我可以说这是一个经典的动态编程问题。您可能会在这里找到一些有趣的文本：

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

和这里

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

score 1 · Accepted Answer

有一种更简单的方法可以找到解决方案：

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

（链接到ideone）

这个想法是通过添加逐渐变大面额的硬币来逐步建立进行更改的方法的数量。外部循环的每次迭代都会遍历我们已经拥有的结果，并且对于可以使用新添加的硬币构造的每个数量，添加可以构造小于当前硬币值的组合的方式的数量。例如，如果当前硬币是5并且当前金额是7，则算法查找2可以构造的方式数，并将其添加到7可以构造的方式数中。如果当前硬币是25并且当前金额是73，则该算法查找构造方法的数目48( 73-25)到先前找到的构造方法数目。73. 最后，里面的数字w[100]代表赚一美元的方法数（292种）。

score 1 · Accepted Answer

我真的相信有人必须提出最有效和最简单的实现，这是对 lenik 答案的改进：
内存：恒定
运行时间：将 100 视为n，然后运行时间约为 O(n (lg(n))) <-我不确定

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;

我认为这可以在恒定时间内解决，因为任何序列和都可以用线性公式表示。

score 0 · Accepted Answer

问题可能是无限递归。您不会在任何地方增加 c 并且循环以 c<=100 运行

编辑1：我不确定是否

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

实际上超过了 100。请确认

编辑 2：我错过了正确初始化的 Sum，并在下面的评论中更正了。

编辑 3： 调试方法- 您可以做的另一件事是，为这棵树编写一个打印函数，或者更确切地说，随着现有代码的深入，在每个级别上打印。添加一个计数器，在总共 10 次迭代后终止循环。打印件会告诉您是否收到垃圾值或您的 c 正在朝着正确的方向逐渐增加。

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

6 回答 6

Related

Reference