ダイナミックプランニング練習3

今日、ダイナミックな計画の中で最も有名な問題の一つであるリュックサックの問題を解決します.
リュックサック問題の記述は、V容量のリュックサックとN個の物品が知られており、i個目の物品の重量はw[i]、収益はc[i]である.
質問:リュックサックの容量を超えない場合、最大どれだけの価値や収益を得ることができますか.
まず状態表現方程式を見つけなければならない.まず、タイトルに記載されている2つの状態を見てみましょう.容量、収益、そして最後に要求された、リュックサックの容量がVの場合、iつの品物がリュックサックに入った最大収益です.1つの配列f[i][j]で示すように、容量jの場合、i個の物品をリュックサックに入れる最大の収益を考えやすい.
状態方程式を見つけました(実は問題の配列表現で、普通は1次元配列あるいは2次元配列です)、それから状態方程式の変換公示を見つけるべきです.個人は実際に状態方程式を探すのが比較的に重要だと思って、状態方程式を探して、変換公示は比較的に容易です.
まず、前のi-1個の物品をすべての容量のリュックサックに入れる最大収益はすでに計算されています(動的計画の中の仮定)、それではどのようにi-1個の物品を容量jのリュックサックに入れることを求めますか?
まず確認すべき点は、i個の物品に容量jのリュックサックを入れる最大収益を求めることであり、i-1のみに関係し、i-2とは関係なく、i-2はf[i-1]を求める際に確認されているためである.
荷物をリュックサックに入れるには、置くか、置かないかの2つがあります.放さないか放さないとf[i][j]はf[i-1][j]に等しいはずで、放すとf[i][j]=max{f[i-1][j-w(i)]+c[i],f[i-1][j]};
なぜか説明します:まず、i番目の品物をリュックサックに入れると、リュックサックには十分な空きスペースが必要です.リュックサックの中から1つのものを取り除く必要はありません.f[i-1][j-w(i)]はどういう意味ですか.これは、前i-1個の物品を容量j-w(i)のリュックサックに入れたときに得られる最大収益であり、c(i)を加えることで、i番目の物品をリュックサックに入れた最大収益である.
f[i-1][j]は、i番目のアイテムをリュックサックに入れない最大の収益です.両者を大きくすると,前のi個の物品を容量jのリュックサックに置く最大の収益である.
実はこれは欲張り法に似ています...しかし、彼は二次元貪欲だ.もし品物が3つで、リュックサックの容量が3であれば、彼の処理の流れはこうです.
ステップ1
前の1つのアイテムの容量が1のリュックサックの最大収益を計算します
ステップ2
前の1つのアイテムの容量が2のリュックサックの最大収益を計算します
ステップ3
前の1つのアイテムの容量が3のリュックサックの最大収益を計算します
ステップ4
最初の2つのアイテムの容量が1のリュックサックの最大収益を計算します
ステップ5
最初の2つのアイテムに容量2のリュックサックを入れた最大収益を計算します
ステップ6
最初の2つのアイテムの容量が3のリュックサックの最大収益を計算します
ステップ7
最初の3つのアイテムの容量が1のリュックサックの最大収益を計算します
ステップ8
前の3つのアイテムの容量が2のリュックサックの最大収益を計算します
ステップ9
前の3つのアイテムの容量が3のリュックサックの最大収益を計算します
 
各ステップは最適解であり,各ステップはできるだけ前のステップの結果を利用し,最終結果も最適解である.
コード:

/**
 * DPTest2 :       2       
 * 
 *       ：   :      V    N   ， i       w[i]，   c[i]。
 * 
 *   :        ，         
 * 
 *   :            ，            
 * 
 * 
 * 
 * @author xuejupo [email protected]
 * 
 *         create in 2016-1-14   6:59:53
 */

public class DPTest2 {
	//     
	private static final int size = 3;
	//     
	private static final int packSize = 5;
	private int[] w = new int[size + 1];
	private int[] c = new int[size + 1];
	//      
	private int[][] f = new int[size + 1][packSize + 1];
	//   
	{
		for(int i = 0; i < size + 1; i++){
			w[i] = new Random().nextInt(3) % 3 + i;
			c[i] = new Random().nextInt(3) % 3 + i;
		}
		System.out.println("             :");
		for(int i = 1; i < size + 1; i++){
			System.out.print(" "+i+"   ：   "+w[i] + ";   :"+c[i]);
			System.out.println();
		}
	}
	/**
	 * main:
	 * 
	 * @param args
	 *            void     
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		DPTest2 dp = new DPTest2();
		dp.packTest();
		System.out.println(dp.f[size][packSize]);
	}
	
	/**  
	 *   f[i][v]   i         v    ，     
	 *   f[1][1]              1         ，
	 * 
	* packTest1:        
	* void         
	*/
	private void packTest(){
		for(int i = 1; i <= size; i++){
			for(int j = 1; j <= packSize; j++){
				//      j
				if(j >= w[i]){
					f[i][j] = Math.max(f[i - 1][j], f[i - 1][j - w[i]] + c[i]);
				}else{
					f[i][j] = f[i - 1][j];
				}
			}
		}
	}
}

結果:

             :
 1   ：   1;   :2
 2   ：   4;   :4
 3   ：   3;   :4
6