PKU 3400 Dropping the stones
http://poj.org/problem?id=3400
重さci,価値viの石がn個(n<=10)と容器a,bがある。
最初に容器aに石を入れていく。石を入れ続けている容器と石を入れ続けていない容器との重さの差がdを超えたら、石を入れる容器を入れ替える。
このとき、容器bに入る最大の価値はいくらかを求めるというような問題。
石の数が小さいので全ての順番を試してシミュレーション。
int num[10]; int p[10],v[10]; main(){ rep(i,10)num[i]=i; int n,d; cin>>n>>d; rep(i,n)cin>>p[i]>>v[i]; int ans=0; do{ int ap=0,bp=0,av=0,bv=0; bool ina=true; rep(i,n){ if(ina){ ap+=p[num[i]]; av+=v[num[i]]; if(ap>bp+d)ina=false; }else{ bp+=p[num[i]]; bv+=v[num[i]]; if(ap+d<bp)ina=true; } } ans=max(ans,bv); }while(next_permutation(num,num+n)); cout<<ans<<endl; }