PKU 3400-Dropping the stones

PKU

問題概要

N個の石があり，重さがpi，価値がviであるとする．
この石を二人の人A,Bに割り振ることを考える．


石の割り振り方は次のように決まる．

  • 最初は石はAに割り振られる．
  • 以後基本的に前回割り当てられた人と同じ人に石は割り当てられる．
  • このとき，割り当てられた人の持っている石の重さの合計がそうじゃない人と比べてDより大きかったら，石を割り当てる対象を変更する．


Bの得られる価値の最大値を求めろ

解法

10!しか石の割り当て方は無いので全探索する

実装(Java)

import java.util.*;
import java.math.*;
import java.io.*;
import java.util.regex.*;
import static java.lang.Math.*;
import static java.util.Arrays.*;
import static java.lang.System.*;

public class Main {
	Scanner cin;
	int N,D;
	int[] p,v;
	Boolean[] used;
	int ans=0;
	void solve(int turn,int lw,int rw,int rv,int cnt){
		if(cnt==N){
			ans=Math.max(ans,rv);
		}else{
			int tlw,trw,trv,tturn;
			for(int i=0;i<N;i++){
				if(used[i])continue;
				used[i]=true;
				if(turn==0){
					tlw=lw+p[i];
					trw=rw;
					trv=rv;
					if(tlw>trw+D){
						tturn=1;
					}else{
						tturn=0;
					}
				}else{
					tlw=lw;
					trw=rw+p[i];
					trv=rv+v[i];
					if(tlw+D<trw){
						tturn=0;
					}else{
						tturn=1;
					}
				}
				solve(tturn,tlw,trw,trv,cnt+1);
				used[i]=false;
			}
		}
	}
	void run(){
		cin=new Scanner(System.in);
		N=cin.nextInt();
		D=cin.nextInt();
		p=new int[N];
		v=new int[N];
		for(int i=0;i<N;i++){
			p[i]=cin.nextInt();
			v[i]=cin.nextInt();
		}
		used=new Boolean[N];
		for(int i=0;i<N;i++)used[i]=false;
		ans=0;
		solve(0,0,0,0,0);
		printf("%d\n",ans);
	}

	void printf(String format,Object... args){
		System.out.printf(format, args);
	}

	public static void main(String[] args) {
		new Main().run();
	}

}