在A个不同的盒子中放置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;
}

你好！

示例:

以下是关于IT技术的内容，但是算法需要花费很多时间。 也许您知道更快地解决此问题的方法？非常感谢并为造成的麻烦道歉。

- Lu Vue

---

编程语言？可能是C99、C++、C#、Java，还有什么？ - leppie

@leppie：既然原帖称其为“算法”，那么它一定是伪代码 ;) - Fred Foo

@leppie：没关系，我只是想知道算法是怎样的... - Lu Vue

@larsmans：抱歉，在那段代码中有一个错误。我已经在我的问题中进行了更正。 - Lu Vue

我仍然得到 f(6,3,2) 的结果是9。我得到 f(3,2,2) 的结果是3。 - Fred Foo

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)的时间。

注意：答案可能是一个非常大的数字，可以超出任何本地整数类型的范围。

- Wisdom's Wind

---

你不需要比[X+1]的大小更大的记忆化数组。 - Luka Rahne

同意。但这会使代码变得有点复杂。我想2*n的变量已经足够解释技术了。如果您能添加一个可理解的带有x+1记忆的示例，那就太好了。 - Wisdom's Wind

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，创建一个二项式系数表可能会很有用。

- Daniel Fischer

Answer 3

请查看页面底部的公式：http://www.mathpages.com/home/kmath337.htm

- John Donn

---

您是指 C[m+k-s(t,j)-1,m-1] 吗？ - Lu Vue

在底部，您会找到N(k)的公式，它是m个项的交替和，其中m应该是盒子的数量（每个项都是某些二项式系数的乘积）。 - John Donn

John Donn，我不理解这个 :( - Lu Vue

@LuVue 底部只有一个公式。它是纯文本格式，可能难以阅读。这个链接可能会有所帮助：这里。 - ladaghini