USACO - 2.2.2 - Subset Sums

 

原创文章转载请注明出处

摘要：动态规划 ，0-1背包问题

一. 题目翻译

1. 描述：

对于从1到N (1 <= N <= 39) 的连续整数集合，能划分成两个子集合，且保证每个集合的数字和是相等的。举个例子，如果N=3，对于{1，2，3}能划分成两个子集合，每个子集合的所有数字和是相等的：{3} 和 {1,2}

这是唯一一种分法（交换集合位置被认为是同一种划分方案，因此不会增加划分方案总数） 如果N=7，有四种方法能划分集合{1，2，3，4，5，6，7}，每一种分法的子集合各数字和是相等的:

{1,6,7} 和 {2,3,4,5} {注 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}

 

2. 格式：

          INPUT FORMAT:

          (file subset.in)

          输入文件只有一行，且只有一个整数N

          OUTPUT FORMAT:

          (file subset.out)

          输出划分方案总数，如果不存在则输出0。

3. SAMPLE：

          SAMPLE INPUT:

 7

          SAMPLE OUTPUT:

4

          

二.  题解

1. 题意理解（将问题分析清楚，大致用什么思路）：

          题目意思是很清晰的，最主要的是如何将这个问题转化成为我们熟悉的算法问题。先来个小提示，大家想一想0/1背包问题 ~ 

          首先给出输入N我们可以计算出总和sum ，这个sum必须是偶数，如果是奇数则输出"0"。对于这个偶数，我们要做的就是从N个数中找出若干个数使得这些数的合为sum/2，这个问题就是一个0/1背包问题，sum/2为背包的容量，一个数字为一个物品，重量为数字的大小。

 

2. 具体实现（具体实现过程中出现的问题）：

          我们用value[i][j]表示用前i个数字，取的总和为j，共有多少种取法。状态转移方程为value[i][j] = value[i-1][j] + value[i-1][j-i]，取当前数字与不取当前数字共同组成了value[i][j]的情况数。

3. 启示：

          核心其实还是背包问题，对于这种简单包装过的动态规划能找出问题的核心。

三.  代码

/*
ID:fightin1
LANG:JAVA
TASK:subset
*/
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.PrintWriter;
import java.util.Scanner;

public class subset {

	static long[][] value;
	public static void main(String[] args) {
		
//		Scanner in = new Scanner(System.in);
//		PrintWriter pw = new PrintWriter(System.out);
		
		try {
			Scanner in = new Scanner(new BufferedReader(new FileReader(
			"subset.in")));
			PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter(
			"subset.out")));

			int num = in.nextInt();
			int sum = 0;
			sum = (num+1)*num/2;
			if (sum%2==0){
				value = new long[num+1][sum/2+1];
				value[1][1] = 1;
				value[1][0] = 1;
				for (int i=2;i<=num;i++){
					for (int j=0;j<=sum/2;j++){
						if (j-i>=0){
							value[i][j] = value[i-1][j] + value[i-1][j-i];
						}else {
							value[i][j] = value[i-1][j];
						}
					}
				}
				pw.println(value[num][sum/2]/2);
			} else {
				pw.println(0);
			}
			pw.close();
			
		} catch (Exception e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		
	}

}