PKU 3977 Subset
http://poj.org/problem?id=3977
N個の整数の集合が与えられる。
この整数の部分集合で和の絶対値が最小になるようなものの絶対値の最小値と、その集合の要素の個数を求めろというような問題。
絶対値が同じ場合は少ない要素の方を答える。
半分全列挙。
イテレーターがendを指している場合を考え忘れて大分はまっていました。
時間制限がとてもゆるい問題。
int n; ll in[35]; ll abs(ll in){ if(in<0)return -in; return in; } pair<ll,int> solve(){ rep(i,n) cin>>in[i]; ll ans=abs(in[0]); int anum=1; map<ll,int> app; rep(i,(1<<n/2)){ ll sum=0; int num=0; rep(j,n/2) if(i>>j&1){ sum+=in[j]; ++num; } if(!num)continue; pair<ll,int> ta=min(mp(ans,anum),mp(abs(sum),num)); ans=ta.F; anum=ta.S; if(app.count(sum)){ int t=app[sum]; app[sum]=min(num,t); }else app[sum]=num; } rep(i,(1<<n-n/2)){ ll sum=0; int num=0; rep(j,n-n/2) if(i>>j&1){ sum+=in[j+n/2]; ++num; } if(!num)continue; pair<ll,int> ta=min(mp(ans,anum),mp(abs(sum),num)); ans=ta.F; anum=ta.S; map<ll,int>::iterator p=app.lower_bound(-sum); if(p!=app.end()){ ta=min(mp(ans,anum),mp(abs(sum+p->F),num+p->S)); ans=ta.F; anum=ta.S; } if(p!=app.begin()){ --p; ta=min(mp(ans,anum),mp(abs(sum+p->F),num+p->S)); ans=ta.F; anum=ta.S; } } cout<<abs(ans)<<' '<<anum<<endl; return mp(abs(ans),anum); } main(){ while(cin>>n,n){ solve(); } }