Java初解リュックサック問題

Java初解リュックサック問題
クラシックリュックサックの問題:
n個の重量と価値がそれぞれwとvの物品があって、これらの物品の中から総重量がWを超えない物品を選んで、すべての選択案の中で価値の総和の最大値を求めます.
制限条件:1<=n<=100
1<=w,v,<=100
1<= W <=1000
サンプル:
入力:
n=4 {w,v} = {{2,3},{1,2},{3,4},{2,2}} W = 5
出力:
7
解法1:
荷物ごとにバックパックを入れているかどうかを調べてみます
コード:

package thebackage;

/*
 *        
 */
public class FirstB {
	int AW = 0;
	int n;
	int[] weight;
	int[] value;
	public FirstB(int n,int[] weight,int[] value) {
			this.n = n;
			this.weight = weight;
			this.value = value;
	}
	public int FtheMax(int i,int j) {
		
		if (n==i) {
		//      
			AW=0;
		} else if(weight[i]>j){
		//        
			AW=FtheMax(i+1, j);
		} else {
		//           
			AW=max(FtheMax(i+1, j), FtheMax(i+1,j-weight[i])+value[i]);
		}
		return AW;
	}
	
	public int  max(int a,int b) {
		if (a>b) {
			return a;
		}else {
			return b;
		}
		
	}
	public static void main(String[] args) {
			int n=4;
			int w=5;
			int[] value = {3,2,4,2};
			int[] weight = {2,1,3,2};
			FirstB firstB = new FirstB(n, weight, value);
			System.out.println(firstB.FtheMax(0, w));
			
	}

}

この解法探索深さはnであり,各層に2回の分岐が必要であり,最悪O(2^n)の時間が必要である.
解法2記憶化探索による最適化を試みる
コードを先に入力:

package thebackage;

/**
 * 
 * @author linziyu
 *      
 */
public class SecondB {
		
	int n;
	int[] value;
	int[] weight;
	int values = 0;
	int[][] dp = new int[100][100];//      
	
	public SecondB(int n,int[] value,int[] weight) {
			this.n = n;
			this.value = value;
			this.weight = weight;

	}
	
	public int theBest(int i,int weights) {
		if (dp[i][weights]>0) {
		//                
			return dp[i][weights];
		}  
		
		if(i==n){
			values=0;
		} else if (weight[i]>weights) {
			values=theBest(i+1, weights);
		} else {
			values=max(theBest(i+1, weights), theBest(i+1,weights-weight[i])+value[i]);
			
		}
		//         
		return dp[i][weights]=values;
		
	}
	
	public int max(int a,int b) {
		if (a>b) {
			return a;
		} else {
			return b;
		}
	}
	
	
	
	public static void main(String[] args) {
		int n=4;
		int w=5;
		int[] value = {3,2,4,2};
		int[] weight = {2,1,3,2};
		SecondB secondB = new SecondB(n, value, weight);
		System.out.println(secondB.theBest(0,w));
		
	}

}

この最適化により、同じパラメータに対して、1回目の呼び出し時にのみ再帰部分が実行され、2回目以降は直接返され、パラメータの組み合わせがnWに及ばないため、O(nW)の複雑さだけで解決できる.