ダイナミックプランニング法解0-1リュックサック問題

0-1リュックサックの問題:ある泥棒が店を盗んだとき、n件の品物があることに気づいた.i件目の品物の価値vi、重wi.彼は持って行ったものが価値があるほどいいことを望んでいるが、リュックサックの中にはCのものしか入れられないことが多い.どのようなものを持っていくべきで、リュックサックに入れたものの価値が最も大きいですか?この問題が0-1リュックサックと呼ばれているのは、すべてのものが持ち去られたり、持ち去られたりしているからです.あるいは残される;泥棒はある品物の一部だけを持って行ったり、同じ品物を2回持って行ったりしてはいけません.
動的計画法で問題を解くには、次の手順に従います.
1.最適解の性質を探し出す;
2.再帰的に最適値を定義する.
3.最適値を下から上へ計算する.
4.最適値を計算する過程で得られた情報に基づいて、最適解を構築する.

package ch03.book;

/**
 * Resolve 0-1 backpack problem using dynamic planning 
 * @author wanyongquan
 * 
 */
public class Backpack {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] weight = {35, 30, 60, 50, 40, 10, 25};
		int[] profit = {10, 40, 30, 50, 35, 40, 30};
		int[][] maxProfit = new int[weight.length][151];
		backpack(profit, weight, 150, maxProfit);
		int[] solution = new int[weight.length];
		trackback(maxProfit, weight, 150, solution);
		
		// 
		for(int i=0;i0; i--) {
			jMax = Math.min(weight[i] -1, capacity);
			for(int j= 0; j= weight[0]) {
			m[0][capacity] = Math.max(m[1][capacity], m[1][capacity-weight[0]] + value[0]);
		}
		else{
			m[0][capacity] = m[1][capacity];
		}
	}
   /**
    *   backpack          ，      ；
    */
	public static void trackback(int[][]m , int[] weight, int capacity, int [] solution) {
		int n = weight.length-1;
		for(int i = 0; i 0? 1:0;
		
	}
}

実行結果:
  solution:
1   1   0   1   0   1   1
max proft: 170