読者です 読者をやめる 読者になる 読者になる

AOJ 1045 Split Up!

問題文 : 404 Not Found

動的計画法とかするのかなって思ったけど(適当に言ったけど検討つかん)、最近ビットで組み合わせ生成するのにハマっているのでそれを使って解いた。

チームメンバーが高々20名なので最悪計算量O(2^20*20)で求まる。2000万ループくらい。TLEスレスレくらいかなー?と思ってSubmitしたら0.82sで通った。やった。

#include <iostream>
using namespace std;

int abs(int a){return a < 0 ? -a : a;}

int main(){
	int n,a,b;
	int member[20];
	int mi;

	while(cin >> n && n){
		mi = (1<<21); //これは適当に大きい数
		for(int i=0;i<n;i++)cin >> member[i];
		
		for(int i=0;i<(1<<n);i++){
			a = b = 0;
			for(int j=0;j<n;j++){
				if( (1<<j) & i)a+=member[j];
				else b+= member[j];
			}
			mi = min( mi,abs(a-b) );
		}
		cout << mi << endl;
	}
}