momoizeSearch (recursive)

import java.util.*;
public class MemoizeSearch {
  static Scanner stdin;
	static int[] w,v;
	static int n,W;
	static int[][] KNP;
	static int MAX_N = 500, MAX_W = 10000;
	public static void main(String[] args) {
		stdin = new Scanner(System.in);
		new MemoizeSearch();
	}
	private static int[] fees;
	private static int[] days;
	MemoizeSearch(){
		fees = new int[] { 130, 150, 190, 190, 230, 290, 330, 70, 330, 110, 90,
				310, 330, 190, 230, 170 };
		days = new int[] { 9, 12, 20, 23, 27, 33, 31, 9, 30, 9, 6, 34, 34, 22,
				25, 13 };
		
//		 fees = new int[] { 130, 150, 190, 190, 230, 290, 330, 70, 330, 110,
//		 90,
//		 310, 330, 190, 230, 170 , 150, 190, 190, 230, 290, 150, 190, 190,
//		 230, 290, 150, 190, 190, 230, 290, 150, 190, 190, 230, 290, 150, 190,
//		 190, 230, 290,
//		 310, 330, 190, 230, 170 , 150, 190, 190, 230, 290, 150, 190, 190,
//		 230, 290, 150, 190, 190, 230, 290, 150, 190, 190, 230, 290, 150, 190,
//		 190, 230, 290,
//		 310, 330, 190, 230, 170 , 150, 190, 190, 230, 290, 150, 190, 190,
//		 230, 290, 150, 190, 190, 230, 290, 150, 190, 190, 230, 290, 150, 190,
//		 190, 230, 290};
//		 days = new int[] { 9, 12, 20, 23, 27, 33, 31, 9, 30, 9, 6,
//		 34, 34, 22,25, 13 , 31, 9, 30, 9, 6, 31, 9, 30, 9, 6, 31, 9, 30, 9,
//		 6, 31, 9, 30, 9, 6, 31, 9, 30, 9, 6,
//		 34, 34, 22,25, 13 , 31, 9, 30, 9, 6, 31, 9, 30, 9, 6, 31, 9, 30, 9,
//		 6, 31, 9, 30, 9, 6, 31, 9, 30, 9, 6,
//		 34, 34, 22,25, 13 , 31, 9, 30, 9, 6, 31, 9, 30, 9, 6, 31, 9, 30, 9,
//		 6, 31, 9, 30, 9, 6, 31, 9, 30, 9, 6};

		
		n = fees.length;
//		n = stdin.nextInt();
		w = new int[n];
		v = new int[n];
		KNP = new int[MAX_N+1][MAX_W+1];
		for(int i =0 ; i < n; ++i){
//			w[i] = stdin.nextInt();
//			v[i] = stdin.nextInt();
			w[i] = days[i];
			v[i] = fees[i];
		}
//		W = stdin.nextInt();
//		w = new int[n];
//		v = new int[n];
//		KNP = new int[MAX_N+1][MAX_W+1];
//		for(int i =0 ; i < n; ++i){
//			w[i] = 30+i;
//			v[i] = 125+i;
//		}
		W = 100;
		Long s = System.currentTimeMillis();
		System.out.println( solve1() );
		out("etime:" + (System.currentTimeMillis() -s) );
	}
	//メモ化O(n,W)
	int solve1(){
		//初期化
		for(int i=0; i < KNP.length; ++i) Arrays.fill(KNP[i], -1);
		return rec(0,W);
	}
	
	void out(String out){
		System.out.println(out);
	}
	
	int callCount; 
	
	//i番目以降の品物から重さの総和がj以下になるよう選んだ時の総和価値の最大値を返す
	int rec(int i, int j){
		if( KNP[i][j] >= 0 ){
//			out("メモ済み" + callCount++);
			return KNP[i][j]; // メモ済み
		}
		else if( i == n ){ //nは仕事の個数
//			out("もう選べない i " + i + " , j " + j+ " ," + KNP[i][j]);
			return 0; //もう選ぶものが無い
		}
		else if( j < w[i] ) {
//			out("" + i +"番目の品物は積載量オーバー");
			return rec( i+1, j); //i番目の品物は積載量オーバー
		}
		else{
			int one = rec(i+1, j);//i番目の仕事を選ばなかった場合を調べる
      int other = rec(i+1, j-w[i])+v[i];//i番目の仕事を選んだ場合を調べる。上の条件分岐の重量チェックを抜けているのでv[i]はゲットされる
			// j-w[i]は　v[i] の商品を載せたので残りの重量を指している
//			System.out.println("keika: " +one + ", " + other);
			KNP[i][j] = Math.max(one, other);
			return KNP[i][j];
//			return Math.max(one, other);
		}
	}
}