游客 注册 | 登录
中文 | En

3213 - Number Partitioning Problem

通过次数

0

提交次数

0

时间限制 : 10 秒 内存限制 : 128 MB

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 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.

题目输出

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

输入/输出样例

输入格式

10
205
157
133
111
100
91
88
59
47
23
8
635
853
401
868
335
435
704
754
0

输出格式

0
3

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;
}

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;
}

Java解答

import java.util.Scanner;

public class Main {
    public static void main(String args[]){
        long to[]=new long[10];
        //System.out.println("ytfhgaaaaaaaaaaaahggg");
        int tou=0;
        Scanner scan2=new Scanner(System.in);
        while(true)
        {
            long n[]=new long[20];
            int u;
            boolean turn[]=new boolean[20];

           // System.out.println("ytfhghgggh|<"+scan2);
            u=scan2.nextInt();
            //System.out.println("ytfhghggg|<"+u);
            if(u==0) break;
            for(int i=0;i<u;i++)
            {//Scanner scan1=new Scanner(System.in);
                n[i]=scan2.nextLong();

            }
            boolean temp[]=new boolean[20];
            long s=sum(n,turn,u);
            long d=s;
            for(;;)
                if(t(turn ,u))
                {
                    long s1=sum(n,turn,u);
                    long s2=s-s1;
                    long t=com(s1,s2,d);
                    if(t>=0)
                    {
                        d=t;
                        for(int k=0;k<u;k++)temp[k]=turn[k];
                    }
                }
                else
                    break;
            to[tou]=d;
            tou++;
            //System.out.println("ytfhghggg|"+tou);
        }
        //System.out.println("ytfhghggg");
        for(int i=0;i<tou;i++)
            System.out.println(to[i]);
    }
    public static  boolean t(boolean t[],int u)
    {
        for(int i=0;i<u;)
            if(t[i]==false)
            {
                t[i]=true;
                if(i>0)
                    for(int j=0;j<i;j++)
                        t[j]=false;
                return true;
            }
            else i++;
        return false;
    }

    public static long sum(long n[],boolean t2[],int u)
    {
        long sum=0;
        for(int i=0;i<u;i++)
            if(t2[i]==false)sum+=n[i];
        return sum;
    }

    public static long com(long a,long b,long before)
    {
        long c;
        if(a>b)c=a-b;
        else c=b-a;
        if(c>=before)return -1;
        else return c;
    }
}
请先登陆