動的プログラミングの例を使用した 0/1 ナップザック問題の修正

ナップザック問題とは何ですか?

ナップサック問題 アルゴリズムは組み合わせ論において非常に役立つ問題です。スーパーマーケットには n 個の荷物 (n ≤ 100) があり、荷物 i の重量は W[i] ≤ 100 で、値は V[i] ≤ 100 です。泥棒がスーパーマーケットに侵入しましたが、泥棒は M (M ≤ 100) を超える重量を運ぶことはできません。）。ここで解決すべき問題は、泥棒が最も高い価値を得るためにどの荷物を持ち去るかということです。

入力：

最大重量 M と荷物の数 n。
重み W[i] と対応する値 V[i] の配列。

出力：

容量の価値とそれに対応する重量を最大化します。
泥棒がどの荷物を持ち去るのか。

ナップザックアルゴリズムはさらに XNUMX つのタイプに分類できます。

動的計画法を使用した 0/1 ナップザック問題。このナップサックアルゴリズムタイプでは、各パッケージを取得することも、取得しないこともできます。さらに、泥棒は、受け取った荷物の端数を受け取ったり、複数回受け取ったりすることはできません。このタイプは動的計画法で解決できます。
分数ナップザック問題アルゴリズム。このタイプはGreedy Strategyで解決できます。

動的プログラミングを使用してナップザック問題を解決する方法と例

分割統治戦略では、解決する問題をサブ問題に分割します。部分問題はさらに小さな部分問題に分割されます。このタスクは、簡単に解決できるサブ問題が見つかるまで続けられます。しかし、そのような分割の過程では、同じ問題に何度も遭遇する可能性があります。

ナップサック動的計画法の基本的な考え方は、解決したサブ問題の解をテーブルに保存することです。サブ問題に再び直面した場合、再度解決する必要はなく、テーブル内の解を取得するだけで済みます。したがって、動的計画法によって設計されたアルゴリズムは非常に効果的です。

動的プログラミングによって問題を解決するには、次のタスクを実行する必要があります。

最小の部分問題の解決策を見つけます。
最も小さな部分問題の解決策を通じて部分問題の解決策を構築する公式 (またはルール) を見つけます。
部分問題の解決策を格納するテーブルを作成します。次に、見つかった式に従って部分問題の解を計算し、テーブルに保存します。
解決された部分問題から、元の問題の解決策が見つかります。

0/1 ナップサック問題を分析する

動的計画法を使って 0/1 ナップザック問題を解析すると、いくつかの注目点が見つかります。ナップザックアルゴリズムの値は、次の XNUMX つの要素によって決まります。

検討されているパッケージの数
ナップザックに収納できる残りの重量。

したがって、XNUMX つの変数量が存在します。

動的プログラミングを使用すると、次のような有益な情報が得られます。

目的関数は XNUMX つの変数量に依存します
オプションのテーブルは 2 次元のテーブルになります。

B[i][j] を呼び出す場合、パッケージ {1, 2, …, i} を重み制限 j で選択することで可能な最大値になります。

重量制限 M で n 個のパッケージを選択した場合の最大値は B[n][M] です。言い換えると、選択するパッケージが i 個ある場合、ナップザックの最大重量が j のとき、B[i][j] が最適な重量になります。
最適な重みは常に最大重み以下です: B[i][j] ≤ j。

例: B[4][10] = 8。これは、選択する最初のパッケージが 8 つ (4 番目から 1 番目のパッケージ) と最大重量がある場合、最適なケースでは、選択したパッケージの合計重量が 4 であることを意味します。ナップザックの項目は 10 です。4 項目すべてを選択する必要はありません。

B[i][j]を計算する式

入力して、次のように定義します。

W[i]、V[i] はパッケージ i の重みと値になります。ここで、i {1, …, n}。
M は、ナップザックが運ぶことができる最大重量です。

単純に選択できるパッケージが 1 つだけの場合。 j ごとに B[1][j] を計算します。これは、ナップザックの最大重量 ≥ 1 番目の荷物の重量を意味します。

B[1][j] = W[1]

重み制限 j を使用すると、パッケージ {1, 2, …, i – 1, i} の中から最大の値を得る最適な選択には XNUMX つの可能性があります。

パッケージ i が選択されていない場合、B[i][j] は、重み制限 j を持つパッケージ {1, 2, …, i – 1} の中から選択することによって可能な最大値になります。あなたが持っている：

B[i][j] = B[i – 1][j]

パッケージ i が選択されている場合 (もちろん、W[i] ≤ j の場合のみ考慮してください)、B[i][j] は、パッケージ i の値 V[i] に、以下から選択して取得できる最大値を加えた値に等しくなります。重量制限 (j – W[i]) のあるパッケージ {1, 2, …, i – 1}。つまり、あなたが持っている価値に関しては次のようになります。

B[i][j] = V[i] + B[i – 1][j – W[i]]

可能な最大値である B[i][j] が作成されるため、B[i][j] は上記 2 つの値の最大値になります。

動的計画法の基礎

したがって、パッケージ i を選択する方が良いかどうかを検討する必要があります。そこから、次のような再帰式が得られます。

B[i][j]= max(B[i – 1][j], V[i]+B[i – 1][j – W[i]]

B[0][j] = 0 パッケージ = 0 から選択することで可能な最大値であることが簡単にわかります。

オプションの表を計算する

上記の再帰式に基づいてオプションのテーブルを作成します。結果が正しいかどうかを確認するには (正確でない場合は、目的関数 B[i][j] を再構築します)。目的関数 B[i][j] とオプションのテーブルを作成することで、トレースの方向を決定します。

オプションのテーブル B には n + 1 行、M + 1 列が含まれます。

まず、動的計画法の基礎を埋め込みます。行 0 にはすべて XNUMX が含まれます。
再帰式を使用して、すべての行が計算されるまで、行 0 を使用して行 1 を計算し、行 1 を使用して行 2 を計算します。

トレース

オプションの表を計算するときは、重量制限 M を持つ n 個のパッケージすべてを選択したときに得られる最大値である B[n][M] に関心があります。

If B[n][M] = B[n – 1][M] パッケージ n が選択されていない場合は、B[n – 1][M] をトレースします。
If B[n][M] ≠ B[n – 1][M]の場合、最適な選択にはパッケージ n とトレース B[n – 1][M – W[n]] があることがわかります。

オプションの表の行 0 に到達するまでトレースを続けます。

選択されたパッケージを見つけるためにオプションのテーブルを検索するアルゴリズム

注: B[i][j] = B[i – 1][j] の場合、パッケージ i は選択されません。 B[n][W]はナップザックに入れた荷物の最適な合計値です。

トレースの手順:

ステップ 1: i = n、j = M から始めます。
ステップ 2: 列 j を下から上に見て、B[i][j] > B[i – 1][j] となる行 i を見つけます。選択したパッケージ i をマークします: [i] = true を選択します。
ステップ 3: j = B[i][j] – W[i]。j > 0の場合はステップ2へ、それ以外の場合はステップ4へ
ステップ 4: 選択したパッケージを印刷するためのオプションの表に基づきます。

Java CPコード

public void knapsackDyProg(int W[], int V[], int M, int n) {
	int B[][] = new int[n + 1][M + 1];
	
	for (int i=0; i<=n; i++)
		for (int j=0; j<=M; j++) {
			B[i][j] = 0;
		}
	
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j <= M; j++) {
			B[i][j] = B[i - 1][j];
			
			if ((j >= W[i-1]) && (B[i][j] < B[i - 1][j - W[i - 1]] + V[i - 1])) {
				B[i][j] = B[i - 1][j - W[i - 1]] + V[i - 1]; 
			}
			
			System.out.print(B[i][j] + " ");
		}
		System.out.print("\n");
	}
	
	System.out.println("Max Value:\t" + B[n][M]);
	
	System.out.println("Selected Packs: ");
	
	while (n != 0) {
		if (B[n][M] != B[n - 1][M]) {
			System.out.println("\tPackage " + n + " with W = " + W[n - 1] + " and Value = " + V[n - 1]);
			
			M = M - W[n-1];
		}
		
		n--;
	}
}

ナップサックコードの説明:

テーブル B[][] を作成します。各セルのデフォルト値は 0 に設定します。
テーブル B[][] をボトムアップ方式で構築します。検索式を用いて選択肢表を計算します。
B[i][j]を計算します。パッケージを選択しない場合 i.
次に評価します。パッケージ i を選択すると、B[i][j] をリセットするよりも有益になります。
テーブルを行 n から行 0 までトレースします。
パッケージnを選択した場合。パッケージ n を選択すると、重み M – W[n – 1] のみを追加できます。

このチュートリアルには XNUMX つの例があります。上記のプログラムを実行する Java コードと XNUMX つの例を次に示します。

public void run() {
	/*
	 * Pack and Weight - Value
	 */
	//int W[] = new int[]{3, 4, 5, 9, 4};
	int W[] = new int[]{12, 2, 1, 1, 4};
	
	//int V[] = new int[]{3, 4, 4, 10, 4};
	int V[] = new int[]{4, 2, 1, 2, 10};
	
	/*
	 * Max Weight
	 */
	//int M = 11;
	int M = 15;
	int n = V.length;
	
	/*
	 * Run the algorithm
	 */
	knapsackDyProg(W, V, M, n);
}

出力は次のようになります。

最初の例:

0 0 0 3 3 3 3 3 3 3 3 3 
0 0 0 3 4 4 4 7 7 7 7 7 
0 0 0 3 4 4 4 7 7 8 8 8 
0 0 0 3 4 4 4 7 7 10 10 10 
0 0 0 3 4 4 4 7 8 10 10 11 
Max Value:	11
Selected Packs: 
	Package 5 with W = 4 and Value = 4
	Package 2 with W = 4 and Value = 4
	Package 1 with W = 3 and Value = 3

XNUMX 番目の例:

0 0 0 0 0 0 0 0 0 0 0 0 4 4 4 4 
0 0 2 2 2 2 2 2 2 2 2 2 4 4 6 6 
0 1 2 3 3 3 3 3 3 3 3 3 4 5 6 7 
0 2 3 4 5 5 5 5 5 5 5 5 5 6 7 8 
0 2 3 4 10 12 13 14 15 15 15 15 15 15 15 15
Max Value:	15
Selected Packs: 
	Package 5 with W = 4 and Value = 10
	Package 4 with W = 1 and Value = 2
	Package 3 with W = 1 and Value = 1
	Package 2 with W = 2 and Value = 2