3213 - Number Partitioning Problem

Consider the partition problem: given a set S of n positive integers, partition it into two disjoint subsets S1 and S2 such that the discrepancy

E(S) = |sum(S1) - sum(S2)|

is minimized, where sum(Si) is the sum of Si's elements. Design an exhaustive search algorithm for this problem.

Input

Input includes multiple groups of data. The first line of each group of data is an integer n (10 <= n <= 20). n = 0 means that the input is over. Each of the next n lines has an integer which belongs to a set to be partitioned.

Output

For each test data, output the minimum discrepancy of two subsets into which the test data is partitioned.

Examples

Input

Output

0
3

Hint

原样例数据超出范围，予以更新。

Solution C

// test.cpp : 定义控制台应用程序的入口点。
//

#include <stdio.h>
#include <math.h>
long long S[20];

int bittest(unsigned int num, int bit)
{
	if ((num >> bit & 0x01) == 1)
		return 1;
	else
		return 0;
}

long long sum(long long s[20], unsigned int i, int n){
	long long t = 0;
	for (int j = 0; j < n; j++){
		if (bittest(i, j) == 1){
			t += s[j];
		}
	}
	return t;
}

long long subtract(long long t1,long long t2){
	if (t1>t2){
		return t1 - t2;
	}
	else{
		return t2 - t1;
	}
}

int main()
{
	int n;
	while (scanf("%d", &n) == 1 && n != 0){
		long long t = 0;
		for (int i = 0; i < n; i++){
			scanf("%ld", &S[i]);
			t += S[i];
		}
		for (unsigned int i = 0; i < (unsigned int)pow(2.0, n - 1); i++){
			long long r = subtract(sum(S, i, n), sum(S, ~i, n));
			if (t>r){
				t = r;
			}

		}
		printf("%lld\n", t);
	}
	return 0;
}

Solution C++

// test.cpp : 定义控制台应用程序的入口点。
//

#include <stdio.h>
#include <math.h>
long long S[20];

int bittest(unsigned int num, int bit)
{
	if ((num >> bit & 0x01) == 1)
		return 1;
	else
		return 0;
}

long long sum(long long s[20], unsigned int i, int n){
	long long t = 0;
	for (int j = 0; j < n; j++){
		if (bittest(i, j) == 1){
			t += s[j];
		}
	}
	return t;
}

long long subtract(long long t1,long long t2){
	if (t1>t2){
		return t1 - t2;
	}
	else{
		return t2 - t1;
	}
}

int main()
{
	int n;
	while (scanf("%d", &n) == 1 && n != 0){
		long long t = 0;
		for (int i = 0; i < n; i++){
			scanf("%ld", &S[i]);
			t += S[i];
		}
		for (unsigned int i = 0; i < (unsigned int)pow(2.0, n - 1); i++){
			long long r = subtract(sum(S, i, n), sum(S, ~i, n));
			if (t>r){
				t = r;
			}

		}
		printf("%lld\n", t);
	}
	return 0;
}

Hint

原样例数据超出范围，予以更新。

Time Limit	10 seconds
Memory Limit	128 MB

Discuss Stats

上一题下一题