组合数学 - 糖果问题

Question

组合数学 - 糖果问题

c++algorithmdynamic-programmingcombinatorics

3

我在某个比赛中遇到了这个问题，但还没有想出解决方案。

这个男孩有苹果并放在盒子里。一个盒子里最多不超过N/2个苹果。他可以将糖果放在盒子里的方法有多少种。

所以我想尝试使用DP实现解决方案。以下是我的代码:

#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <unistd.h>
#include <vector>
#define size 1002
using namespace std;

long long a[size][size];
int n, k;
int main()
{
    cin >> n >> k;
    int kk = n/2;

    for(int i = 0; i <= k; ++i)
        a[0][i] = 1;
    a[0][0] = 0;

    for(int i = 0; i <= kk; ++i)
        a[i][1] = 1;

    for(int i = 1; i <= n; ++i) {

        for(int j = 2; j <= k; ++j) {
            int index = 0;
            long long res = 0;
            while(1) {
                res += a[i-index][j - 1];
                index += 1;

                if(index == kk + 1 || i-index < 0)
                    break;
            }
            a[i][j] = res;

        }
    }
    cout << a[n][k] << endl;

}

但问题在于我们的输入中有大量的数字，例如：

2 ≤ N ≤ 1000 是糖果的数量，N - 偶数; 2 ≤ S ≤ 1000 - 是小盒子的数量。

因此，对于像 N = 1000 和 S = 1000 这样的输入，我需要花费 5*10^8 次操作。而且这些数字非常大，所以我必须使用 BigInteger 算法？

也许有一种算法可以在线性时间内实现该问题？谢谢，对我的英语不好感到抱歉！

- Rasul Kerimov

你的代码对于较小的输入是否能够给出正确的结果？ - 463035818_is_not_a_number

@tobi303 是的，对于较小的输入，该解决方案是正确的。 - Rasul Kerimov

1

看一下这篇文章的最后一行，其中给出了一个计算数量的封闭式公式（分别用(N)，(S)，(N/2)代替(k), (m), (R)）。 - collapsar

我猜“在一个小盒子里放置不超过N/2的糖果”应该是指“任何小盒子中的糖果数量都不能超过N/2”，对吗？ - M.M

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Pham Trung · Accepted Answer

你可以通过以下观察将时间复杂度从O(kn^2)降低到O(nk)：

for(int i = 1; i <= n; ++i) {

    for(int j = 2; j <= k; ++j) {
        int index = 0;
        long long res = 0;
        while(1) {
            res += a[i-index][j - 1];
            index += 1;

            if(index == kk + 1 || i-index < 0)
                break;
        }
        a[i][j] = res;

    }
}

对于每个 a[i][j]，我们可以很容易地看出： a[i][j] = sum a[k][j - 1]，其中 k 的范围从 (i - n/2) 到 i 因此，如果我们创建一个数组 sum 来存储前一步所有索引的总和，我们可以从上面的嵌套循环中减少一个循环。 a[i][j] = sum[i] - sum[i - (n/2) - 1]; 伪代码：

long long sum[n + 1];
for(int j = 2; j <= k; ++j) {
    long long nxt[n + 1];
    for(int i = 1; i <= n; ++i) {
        int index = 0;
        long long res = sum[i] - sum[i - (n/2) - 1];

        a[i][j] = res;
        nxt[i] = nxt[i - 1] + a[i][j];//Prepare the sum array for next step

    }
    sum = nxt;
}

注意：上述代码未处理数组sum的初始化步骤，也未处理i < n/2的情况。这些情况应该是易于处理的。

更新：

我的Java解决方案类似地被接受了：

public static void main(String[] args) throws FileNotFoundException {
    // PrintWriter out = new PrintWriter(new FileOutputStream(new File(
    // "output.txt")));
    PrintWriter out = new PrintWriter(System.out);
    Scanner in = new Scanner();
    int n = in.nextInt();
    int s = in.nextInt();
    BigInteger[][] dp = new BigInteger[n + 1][2];
    BigInteger[][] count = new BigInteger[2][n + 1];
    int cur = 1;
    for (int i = 0; i <= n / 2; i++) {
        dp[i][0] = BigInteger.ONE;
        count[0][i] = (i > 0 ? count[0][i - 1]  : BigInteger.ZERO)
                .add(dp[i][0]);

    }
    for (int i = n / 2 + 1; i <= n; i++) {
        dp[i][0] = BigInteger.ZERO;
        count[0][i] = count[0][i - 1];
    }
    for (int i = 2; i <= s; i++) {
        for (int j = 0; j <= n; j++) {

            dp[j][cur] = dp[j][1 - cur].add((j > 0 ? count[1 - cur][j - 1]
                    : BigInteger.ZERO)
                    .subtract(j > n / 2 ? count[1 - cur][j - (n / 2) - 1]
                            : BigInteger.ZERO));

            count[cur][j] = (j > 0  ? count[cur][j - 1] : BigInteger.ZERO)
                    .add(dp[j][cur]);
        }
        cur = 1 - cur;
    }
    out.println(dp[n][1 - cur]);
    out.close();
}