AOJ 1045 - Split Up!

Split Up! | Aizu Online Judge

・概要
n個の正の整数が与えられた時，それらを2つのグループに分けてそれぞれのグループの整数の和をとったとき，それらの差が最小となるときの値を求める

(n<=20)
各々の整数は1000000未満

・アイデア
n個の整数の合計sumとして，sum/2以下で最大にできる選び方を考えよう
これはメモ化再起でいけるかな?と思ったけどその合計値をテーブルに入れねばならないということを最近学んだ(これを知らないでずっと止まってた)
でも全探索したら2^20だしちょっと動くか不安じゃない?(2^20=1048576だから動いたかも)
枝刈りが効果あるかも(sum/2で打ち止めだから結構効果はあるはず)

・実装

#include <cstdio>
#include <iostream>
using namespace std;

int n;
long m, sum, a[20];

//sum/2以下で最も高い戦闘力の合計
void rec(int x, long y){ //x人目を入れるか入れないか,今の戦闘力y
	if(x==n){
		if(m<y) m=y;	
	}
	else{
		if(y+a[x]>sum/2) rec(x+1,y);
		else{
			rec(x+1,y+a[x]);
			rec(x+1,y);		
		}	
	}
	
}

int main(){
	while(1){
		scanf(" %d", &n);
		if(n==0) break;
		
		sum=0;
		for(int i=0; i<n; ++i){
			scanf(" %ld", &a[i]);
			sum+=a[i];
		}
	
		m=0;	
		rec(0, 0);
		
		long mm=sum-m;
		//printf("m=%ld, mm=%ld\n",m ,mm);
		printf("%ld\n", mm-m);
	}
}

かなり時間に余裕を持って動きました...ものは試し。