在不同的盒子中的N个相同球的组合

Question

int f(int n,int a,int x)
{
        if(a==1)
        {
            if(n>=0 && n<=x)  //HERE WAS ERROR,sorry
                return 1;
            else 
                return 0;
        }

        int ans=0;

        for(int i=0;i<=x;i++)
            ans += f(n-i,a-1,x);

    return ans;
}

你好！

例：

这是算法，但它花了很多时间。也许你知道更快的方法来解决这个问题？非常感谢，抱歉担心。

Answer 1

你需要的是动态编程。您需要为已经计算过的参数记住函数f的值。它也可以在没有递归的情况下实现，如下所示：

int f(int n,int a,int x)
{
    int q[1000][50]; // to simplify and not use dynamic allocation assume that a < 50 and n < 1000

    q[0][0] = 1;
    for (int i = 1; i < 1000; ++i)
        q[i][0] = 0;

    for (int i = 1; i <= a; ++i)
    {
        for (int j = 0; j <= n; j++)
        {
            int t = 0;
            for (int l = 0; l <= j && l <= x; ++l)
                t += q[j - l][i-1];
            q[j][i] = t;
        }
    }

    return q[n][a];
}

这只是简单的技术演示。它可以再次优化，你可以预先计算t-sum并消除l的循环。而且你不必存储整个表q，你只需要两层，它会减少内存使用量。所以结果看起来像这样：

int f(int n,int a,int x)
{
    int q[1000][2]; // to simplify and not use dynamic allocation assume n < 1000

    q[0][0] = 1;
    for (int i = 1; i < 1000; ++i)
        q[i][0] = 0;

    int current = 1;
    for (int i = 1; i <= a; ++i)
    {
        int t = 0;
        for (int j = 0; j <= n; j++)
        {
            t += q[j][1 - current];
            if (j > x)
                t -= q[j - x - 1][1 - current];

            q[j][current] = t;
        }
        current = 1 - current;
    }

    return q[n][1 - current];
}

所以最后需要花费O（a * n）时间来计算。

PS：请注意，答案可能是一个巨大的数字，可以溢出任何本机整数类型。

Answer 2

首先，如果A*X < N，没有办法分发球，所以你可以提前停止。如果A*X == N，只有一种方式。然后，首先选择放置X球并以较小限制重复的盒子数量可能会更快。

int f(int n, int a, int x){   // should all be unsigned, actually
    if (n == 0){
        return 1;
    }
    int p = a*x;
    if (p < n){
        return 0;
    }
    if (p == n){
        return 1;
    }
    if (x == 1){
        return binom(a,n);    // ways to choose n boxes from a boxes
    }
    // now the interesting cases
    int ways = 0;    // should perhaps be unsigned long long, that number grows fast
    int xCount, tempRes, min, max;
    min = a+n-p;
    if (min < 0) min = 0;
    max = n/x;
    for(xCount = min; xCount <= max; ++xCount){
        tempRes = f(n - x*xCount,a - xCount, x-1); // ways to distribute the remaining balls
        ways += binom(a,xCount)*tempRes;    // multiply by the number of ways to choose xCount boxes
    }
    return ways;
}

如果经常调用f，为二项式系数创建表可能很有用。

Answer 3

看看http://www.mathpages.com/home/kmath337.htm和页面底部的公式。