当前位置:首页 » Project Euler » 详细页

Subsets with a unique sum 题号:201 难度: 65 中英对照

For any set A of numbers, let sum(A) be the sum of the elements of A.
Consider the set B = {1,3,6,8,10,11}.
There are 20 subsets of B containing three elements, and their sums are:

sum({1,3,6}) = 10,
sum({1,3,8}) = 12,
sum({1,3,10}) = 14,
sum({1,3,11}) = 15,
sum({1,6,8}) = 15,
sum({1,6,10}) = 17,
sum({1,6,11}) = 18,
sum({1,8,10}) = 19,
sum({1,8,11}) = 20,
sum({1,10,11}) = 22,
sum({3,6,8}) = 17,
sum({3,6,10}) = 19,
sum({3,6,11}) = 20,
sum({3,8,10}) = 21,
sum({3,8,11}) = 22,
sum({3,10,11}) = 24,
sum({6,8,10}) = 24,
sum({6,8,11}) = 25,
sum({6,10,11}) = 27,
sum({8,10,11}) = 29.

Some of these sums occur more than once, others are unique.
For a set A, let U(A,k) be the set of unique sums of k-element subsets of A, in our example we find U(B,3) = {10,12,14,18,21,25,27,29} and sum(U(B,3)) = 156.

Now consider the 100-element set S = {12, 22, ... , 1002}.
S has 100891344545564193334812497256 50-element subsets.

Determine the sum of all integers which are the sum of exactly one of the 50-element subsets of S, i.e. find sum(U(S,50)).


Solution

动态规划。 设目前集合有$n$个数$\{i^2\}_{i=1}^n$,$dp[n][k][x]$表示$k$元子集的元素和$x$出现的次数。 初始情况是$dp[0][0][0]=1$,其余为$0$。 递推公式:将新加入的元素$e=n^2$加到所有已有的$x$上。 需要注意这里的$x$满足$x\leq maxsum$,$maxsun$是原数列末$K$项的和,表示最大可能的$K$元子集的元素和。 利用滚动数组可以将第一维$n$缩减为$2$。

Code

public final class p201 {
    public static void main(String[] args) {
        long start=System.nanoTime();
        String result = run();        
        long end=System.nanoTime();
        System.out.println(result);
        System.out.println( (end-start)/1000000 + "ms" );
    }

	static final int N = 100;
	static final int K = 50;

    static public String run() {
		// initialize S
		int[] S = new int[N];
		for (int n = 1; n <= N; n++)
			S[n - 1] = n * n;

		// compute maxsum and minsum
		int maxsum = 0;
		int minsum = 0;
		for (int n = 0; n < K; n++) {
			minsum += S[n];
			maxsum += S[N - n - 1];
		}

		// initialize x and y
		int[][] x = new int[K + 1][maxsum + 1];
		int[][] y = new int[K + 1][maxsum + 1];
		y[0][0] = 1;

		// bottom-up DP over n
		for (int n = 1; n <= N; n++) {
			x[0][0] = 1;
			for (int k = 1; k <= K; k++) {
				int e = S[n - 1];
				for (int s = 0; s < e; s++)
					x[k][s] = y[k][s];
				for (int s = 0; s <= maxsum - e; s++) {
					x[k][s + e] = y[k - 1][s] + y[k][s + e];
				}
			}
			int[][] t = x;
			x = y;
			y = t;
		}

		// sum of unique K-subset sums
		int sum = 0;
		for (int s = minsum; s <= maxsum; s++) {
			if (y[K][s] == 1)
				sum += s;
		}
		return ""+sum;
	}


}
115039000
13956ms