问题描述
我正在尝试从USACO培训网关中解决子集...
I am trying to solve subsets from the USACO training gateway...
问题陈述
对于从1到N的许多连续整数集（1
For many sets of consecutive integers from 1 through N (1 <= N <= 39), one can partition the set into two sets whose sums are identical.
例如，如果N = 3，则可以用一种方式对集合{1、2、3}进行分区，以使两个子集的总和相同：
For example, if N=3, one can partition the set {1, 2, 3} in one way so that the sums of both subsets are identical:
{3}和{1,2}
这被视为单个分区（即，将订单计数反转为相同的分区，因此不会增加计数分区）。
{3} and {1,2}This counts as a single partitioning (i.e., reversing the order counts as the same partitioning and thus does not increase the count of partitions).
如果N = 7，则有四种方式对集合{1,2,3，... 7}进行分区，以使每个分区具有相同的总和：
If N=7, there are four ways to partition the set {1, 2, 3, ... 7} so that each partition has the same sum:
{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。
{1,6,7} and {2,3,4,5}{2,5,7} and {1,3,4,6}{3,4,7} and {1,2,5,6}{1,2,4,7} and {3,5,6}Given N, your program should print the number of ways a set containing the integers from 1 through N can be partitioned into two sets whose sums are identical. Print 0 if there are no such ways.
您的程序必须计算答案，而不是从表中查找答案。
Your program must calculate the answer, not look it up from a table.
结束
在我运行O（N * 2 ^ N）通过简单地对集合进行排列并找到总和。
Before I was running on a O(N*2^N) by simply permuting through the set and finding the sums.
找出那是多么可怕的低效率，我继续映射总和序列...
）
Finding out how horribly inefficient that was, I moved on to mapping the sum sequences...http://en.wikipedia.org/wiki/Composition_(number_theory)
在遇到很多编码问题以至于无法重复之前，它仍然太慢，所以我回到正题：（。
After many coding problems to scrape out repetitions, still too slow, so I am back to square one :(.
现在，我更加仔细地研究这个问题，看来我应该设法找到一种方法来求和而不是求和，但实际上是通过某种公式直接求和的数量。
Now that I look more closely at the problem, it looks like I should try to find a way to not find the sums, but actually go directly to the number of sums via some kind of formula.
如果有人可以给我提供有关如何解决此问题的指导，那我就不胜枚举。我用Java，C ++和python编程。
If anyone can give me pointers on how to solve this problem, I'm all ears. I program in java, C++ and python.
推荐答案
实际上，有一个更好，更简单的解决方案，您应该使用
。在您的代码中，您将有一个整数数组（其大小为总和），其中索引 i 上的每个值代表可能的数字分区方式，以便其中一个分区具有一个 i 的总和。这是您的代码在C ++中的样子：
Actually, there is a better and simpler solution. You should use Dynamic Programminginstead. In your code, you would have an array of integers (whose size is the sum), where each value at index i represents the number of ways to possibly partition the numbers so that one of the partitions has a sum of i. Here is what your code could look like in 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）解决方案，到目前为止
This gives you an O(N^3) solution, which is by far fast enough for this problem.
我尚未测试此代码，因此可能存在语法错误或某些错误，但是您明白了。让我知道是否还有其他问题。
I haven't tested this code, so there might be a syntax error or something, but you get the point. Let me know if you have any more questions.
这篇关于USACO：子集（低效）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！