我正在尝试从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 回答
实际上,有一个更好,更简单的解决方案 . 你应该使用Dynamic Programming代替 . 在您的代码中,您将拥有一个整数数组(其大小为总和),其中索引i处的每个值表示可能对数字进行分区的方式的数量,以便其中一个分区的总和为i . 以下是您的代码在C中的样子:
这给你一个O(N ^ 3)解决方案,这个问题足够快了 .
我没有测试过这段代码,因此可能存在语法错误或其他问题,但您明白了 . 如果您还有其他问题,请与我们联系 .
这与在多项式中找到系数x ^ 0项(x ^ 1 1 / x)(x ^ 2 1 / x ^ 2)...(x ^ n 1 / x ^ n)相同,这应该是取大约O(n ^ 3)的上限 .