USACO:子集(低效)

我正在尝试从USACO培训网关解决子集...

Problem Statement

对于从1到N(1 <= N <= 39)的许多连续整数集合,可以将该集合划分为两个集合,其总和相同 .

例如,如果N = 3,则可以以一种方式对集合{1,2,3}进行分区,以使两个子集的总和相同:

{3}和{1,2}这被视为单个分区(即,将顺序颠倒为相同的分区,因此不会增加分区的数量) .

如果N = 7,有四种方法可以对集合{1,2,3,... 7}进行分区,以便每个分区具有相同的总和:

{1,6,7}和{2,3,4,5} {2,5,7}和{1,3,4,6} {3,4,7}和{1,2,5,6 } {1,2,4,7}和{3,5,6}给定N,你的程序应该打印包含从1到N的整数的集合的方式的数量可以被分成两个总和相同的集合 . 如果没有这样的方法,请打印0 .

您的程序必须计算答案,而不是从表中查找 .

End

在我运行O(N * 2 ^ N)之前,只需通过集合排列并找到总和 .

找出效率如此可怕的低效率,我继续绘制和序列的映射...... [http://en.wikipedia.org/wiki/Composition_(number_theory](http://en.wikipedia.org/wiki/Composition_(number_theory))

经过多次编码问题来重复,仍然太慢,所以我回到原点:( .

现在我更仔细地研究这个问题,看起来我应该试图找到一种找不到总和的方法,但实际上通过某种公式直接得到总和的数量 .

如果有人能指点我如何解决这个问题,我全都听见了 . 我用java,C和python编程 .

回答(2)

2 years ago

实际上,有一个更好,更简单的解决方案 . 你应该使用Dynamic Programming代替 . 在您的代码中,您将拥有一个整数数组(其大小为总和),其中索引i处的每个值表示可能对数字进行分区的方式的数量,以便其中一个分区的总和为i . 以下是您的代码在C中的样子:

int values[N];
int dp[sum+1]; //sum is the sum of the consecutive integers

int solve(){
    if(sum%2==1)
        return 0;
    dp[0]=1;
    for(int i=0; i<N; i++){
        int val = values[i]; //values contains the consecutive integers
        for(int j=sum-val; j>=0; j--){
            dp[j+val]+=dp[j];
        }
    }
    return dp[sum/2]/2;
}

这给你一个O(N ^ 3)解决方案,这个问题足够快了 .

我没有测试过这段代码,因此可能存在语法错误或其他问题,但您明白了 . 如果您还有其他问题,请与我们联系 .

2 years ago

这与在多项式中找到系数x ^ 0项(x ^ 1 1 / x)(x ^ 2 1 / x ^ 2)...(x ^ n 1 / x ^ n)相同,这应该是取大约O(n ^ 3)的上限 .