常用アルゴリズム——動的計画アルゴリズム

ダイナミックプランニングアルゴリズム
アルゴリズムの紹介

動的計画(Dynamic Programming)アルゴリズムの核心思想は、大きな問題を小さな問題に分けて解決し、最適解を一歩一歩取得する処理アルゴリズム

である.

動的計画アルゴリズムは分治アルゴリズムと類似しており、その基本思想も解くべき問題をいくつかのサブ問題に分解し、まずサブ問題を解き、その後、これらのサブ問題の解から元の問題の解を得る.

は分治法と異なり,動的計画で解くのに適した問題であり,分解して得られるサブ問題は互いに独立していないことが多い.(すなわち、次のサブフェーズの解は、前のサブフェーズの解に基づいて、さらなる解を行う)

.

動的計画は、表を記入することによって徐々に推進され、最適解を得ることができる.

アルゴリズムのケース(リュックサックの問題)
1つのリュックサックがあり、容量容量は4で、現在は以下の物品があり、リュックサックの容量の最大値を達成することが要求され、しかも超えず、物品は繰り返してはならない.
アイテム
じゅうりょう
価格
ギター(G)
1
1500
音響(S)
4
3000
コンピュータ(L)
3
2000
アルゴリズムの主な思想は,動的計画を利用して解決する.毎回遍歴したi番目のアイテムは、w[i]とv[i]に基づいてリュックサックに入れる必要があるかどうかを決定します.すなわち、与えられたn個の物品について、v[i]、w[i]をそれぞれ第個の物品の価値と重量とし、Cをリュックサックの容量とする.さらにv[i][j]は、前のiつの物品に容量jのリュックサックを入れることができる最大の価値を示す.次の結果が得られます.

v[i][0]=v[0][j]=0;//記入されたテーブルの最初の行と最初の列が0

であることを示す.

w[i]>jの場合:v[i][j]=v[i-1][j]//新たに追加する商品の容量が現在のリュックサックの容量より大きい場合、前のセルの読み込みポリシー

をそのまま使用する

j>=w[i]の場合:v[i][j]=max{v[i-1][i],v[i-1][j-w[i]+v[i]}//v[i-1][j]:前のセルが転入した最大値を表す.v[i]:現在の商品の価値を示す

表に変換
アイテム
0ポンド
1ポンド
2ポンド
3ポンド
4ポンド
0
0
0
0
0
ギター(G)
0
1500G
1500G
1500G
1500G
音響(S)
0
1500G
1500G
1500G
3000S
コンピュータ(L)
0
1500G
1500G
2000L
2000L+1500G
コード実装

package com.dynamic;
public class KnapsackProblem {
	public static void main(String[] args) {
		int[] w = { 1, 4, 3 };//      
		int[] val = { 1500, 3000, 2000 };//     
		int m = 4;//      
		int n = val.length;//     
		//       
		// v[i][j]    i          j          
		int[][] v = new int[n + 1][m + 1];
		//          
		int[][] path = new int[n + 1][m + 1];
		//           
		for (int i = 0; i < v.length; i++) {
			v[i][0] = 0;//       0
		}
		for (int i = 0; i < v[0].length; i++) {
			v[0][i] = 0;//        0
		}
		//              
		for (int i = 1; i < v.length; i++) {
			for (int j = 1; j < v[0].length; j++) {
				if (w[i - 1] > j) {//   i  1   ，      w[i]   w[i-1]
					v[i][j] = v[i - 1][j];
				} else {
					//   i 1  ，  val[i-1] w[i-1]
					// v[i][j] = Math.max(v[i - 1][j], val[i - 1] + v[i - 1][j - w[i - 1]]);
					if (v[i - 1][j] < val[i - 1] + v[i - 1][j - w[i - 1]]) {
						v[i][j] = val[i - 1] + v[i - 1][j - w[i - 1]];
						path[i][j] = 1;
					} else {
						v[i][j] = v[i - 1][j];
					}

				}
			}
		}
		//   v
		for (int i = 0; i < v.length; i++) {
			for (int j = 0; j < v[i].length; j++) {
				System.out.print(v[i][j] + " ");
			}
			System.out.println();
		}
		//            
		int i = path.length - 1;//      
		int j = path[0].length - 1;//      
		while (i > 0 && j > 0) {//  path      
			if (path[i][j] == 1) {
				System.out.printf(" %d       
", i);
				j -= w[i - 1];
			}
			i--;
		}
	}
}