USACO/subset

分析一

(优化【非解】) n个数的总和为sum:=n*(n+1)shr 1,当且仅当sum为偶数的时候才有解，sum为奇数时直接输出0并且退出程序；但是这样做了也还是会超时。所以要进行优化处理。 经计算 只有n=4K 和n=4K-1 （K属于正整数）时才有解 不然直接输零 也不用计算了。

分析二

动态规划 设分成的子集为set1,set2,sum=(n*(n+1)div 2)div 2. 设f[i,j]表示取前i个数，使set1总数和为j的方案数.第i个数的值为i,根据是否取第i个数就有:

  f[i,j]=f[i-1,j]+f[i-1,j-i]    j-i>=0 
  f[i,j]=f[i-1,j]               j-i<0 

那么,最后结果为f[n,sum] dp步骤为：

  f[1,1]:=1;
  f[1,0]:=1;
  for i:=2 to n do
   for j:=0 to sum do
    if j-i>=0 then f[i,j]:=f[i-1,j]+f[i-1,j-i]
    else f[i,j]:=f[i-1,j];

则最后的结果为f[n,sum] div 2.

{其实就是01背包求方案数} 分析为什么它是0\1背包：将一个集合划分成 两个“元素总和相等”的集合，设原集合的元素总和为sum，则划分后的集合的元素综合都为sum/2。那么我们可以把sum/2看成背包的容量，原集合中的数字看为物品的重量及价值（这里价值维度可以淡化，就像装箱问题）。则原问题转化为 “从原集合中选出n个物品，使这n个物品恰好放满容量为sum/2的背包的方案总数”。

可以用类似于01背包的方法来优化空间复杂度，只不过j要倒序，代码如下：

  f[1]:=1;f[0]:=1;
    for i:=2 to n do 
      for j:=sum downto 0 do
        if j-i>=0 then f[j]:=f[j]+f[j-i];

分析三

递推 设ans[i,x]表示在前个i元素里选择若干使其和为x的选法

有ans[i,x]=ans[i-1,x]+ans[i-1,x-i]

最后的输出就是ans[n-1,((n+1)*n div 4)-n]

注意解不存在的情况单独判断,详细方法看分析一；

由于这道题的数据范围只是 n≤39，所以用二维数组并不会超出空间，但是这里完全可以使用一维数组，只是需要倒序扫描就好。

分析四

母函数求解，效率高，空间小的说，首先我们对问题进行转化，很明显只有当1到n的总和为偶时才有可能分成和相等的两堆。假设可以分成相等的两堆，每堆之和为HalfSum,问题就可以转化为用1到n的数取任意个出来相加使它们的和等于HalfSum，并且每个数字只有一个，是不是很像有重量为1到n的砝码n个，每种一个，称出HalfSum的重量的方法有多少种？又由于1到n个数的总和为2*HalfSum所以选出另外未被选出来组合成HalfSum的数相加也是HalfSum，最后把方法数除2即为答案！！！

母函数：G(x) = (1+x)*(1+x^2)*(1+x^3)*(1+x^4)………………*(1+x^n) 模拟这个多项式运算即可，代码贴于C++
中，作者：long5011.Edit by coderling。blog: http://coderling.comuf.com

分析五

动态规划，mat[i][j]表示前i个数组成的两个子集的差的绝对值为j的方案数，例如mat[1][1]表示数字1形成两个集合，两个集合只能是一个为空集，一个仅含元素1.所以初始时mat[1][1]=1;则mat[m][n] = mat[m-1][m]; 然后从1~N循环，每次更新第i行的数值，最后输出mat[N][0]即可

void work()
{
     for(int i=2; i!=N+1; ++i)
     {
         for(int j=0; j!=C; ++j)
         {
             if(mat[i-1][j]!=0)
             {
                 //system("pause");
                 mat[i][abs(j-i)] += mat[i-1][j];
                 mat[i][abs(i+j)] += mat[i-1][j];
             }
         }
     }
}

分析六

动态规划，使用三维数组。

要求两集合相等，可得知两集合内元素总和均为所有元素总和的一半。可求集合中元素值的总和，在此定为k。当然如果k不是整数，则直接输出0。k的计算公式：k=((1+n)*n)/4 既等差数列求和的一半啦！

d[i][j][p]表示在前i个数中取j个数，得到总和是p的可能总数。

方程：d[i][j][p]=d[i-1][j][p]+d[i-1][j][p-i];

既从i-1个数中取j个数得到p的可能，加上i-1个数得到p-i（在此步中取i）的可能数之和。

注意i-1小于p时，不加前面一项；p-i<0时，不加后面一项。

初始条件仅需考虑d[1][1][1]=1;

最后结果为 d[n][i][k],i=0...n求和（输入公式实在不会用啊……）

既从n个数中取i个，i<=n，得到k所有可能之和，注意k为前面所求出的总和。

d[1][1][1]=1;
for(int p=1;p<=k;p++)
{
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=i;j++)
		{
			if(i-1>=j)
				d[i][j][p]=d[i-1][j][p];
			if(p-i>=0)
				d[i][j][p]+=d[i-1][j][p-i];
		}
	}
}
int sum=0;
for(int i=1;i<=n;i++)
{
	sum+=d[n][i][k];
}

代码较混乱，将就着看吧。

暴力剪枝做法

我要吐槽!你们都没有用暴力做的吗!N的范围这么小!

我们设T=12(你也可以选点别的值,不过建议大一点,小了会TLE)

当N<=T的时候 直接暴力出答案

N>T的时候 我们还是搜索 但终止边界为T

此时直接答案+=T=12的答案就好了

好像有点dp的思想 但这不是dp 这只是个暴力搜索剪枝而已

参考代码

C
C++
Pascal
Java

引用

[1]

[2]