首页 文章

USACO:子集(低效)

提问于
浏览
-2

我正在尝试从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 回答

  • 0

    实际上,有一个更好,更简单的解决方案 . 你应该使用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)解决方案,这个问题足够快了 .

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

  • 1

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

相关问题