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

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

その ナップサック問題 これは古典的な組み合わせ最適化問題です。スーパーマーケットは n パッケージ (n ≤ 100)。パッケージ i 重量 W[i] ≤ 100、価値 V[i] ≤ 100 の荷物があります。泥棒は最大重量 M (M ≤ 100) を超える荷物を運ぶことはできません。泥棒はどの荷物を持って行けば合計価値を最大化できるでしょうか？

入力：

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

出力：

• 容量内で得られる最大総額。
• 泥棒が盗むべき荷物の正確なセット。

ナップサックアルゴリズムは、よく知られている2つの変種に分けられます。

• 0/1 ナップサック問題 動的計画法によって解決される。各パッケージは、丸ごと受け取るか、残すかのどちらかであり、端数や重複は認められない。
• 分数ナップザック問題 貪欲法によって解決されます。ここでは、残りの容量を埋めるために、任意のパッケージの一部を取得できます。

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

分割統治法は、大きな問題を小さな部分問題に分割し、それぞれの部分問題が簡単に解決できるようになるまで分割を続けます。一方、単純な再帰処理では、同じ部分問題を何度も解決してしまうことが多く、無駄な労力が発生します。

ナップサック動的計画法の核心的な考え方は、解決済みの部分問題をすべてテーブルに格納することです。繰り返し呼び出しでは、答えを再計算するのではなく読み込むことで、指数関数的な再帰を多項式時間コードに変換します。

動的プログラミングを使用してナップザック問題を解く

動的計画法による解を設計するには、次の4つの手順に従います。

• まずは最も小さな部分問題を解決してください。
• より小さな問題からより小さな問題の解を構築する漸化式を導出する。
• 部分問題の解答を、漸化式を用いて下から順に計算した表に格納する。
• 記入済みの表から最終的な答えを組み立ててください。

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

最適な値は、2つの独立した要因によって決まります。

1. 現在、いくつのパッケージが検討されていますか？
2. 残りの重量は、リュックサックにまだ収納できる。

目的関数は2つの量に依存するため、選択肢の表は2次元でなければならない。 B[i][j] は、重量制限 j を持つパッケージ {1, …, i} の中から選択する際の最大値を表します。

• 最終的な答えは B[n][M]容量M以下のn個のパッケージ全体で最高の合計値。
• 選択できる総重量は常に現在の容量によって制限されます。 B[i][j] ≤ j.

例：B[4][10] = 8 の場合、容量 10 以内の最初の 4 つのパッケージから得られる最適な合計重量は 8 です。これらの 4 つのパッケージのうち、いくつかはスキップされる可能性があります。

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

• W[i], V[i] はパッケージ i の重量と価値であり、i は {1, …, n} に含まれる。
• M これは、そのリュックサックが運搬できる最大重量です。

パッケージが1つの基本ケース：容量j ≥ W[1]ごとに：

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

一般的なケースでは、パッケージ i を容量 j に含めるかどうかを決定してください。

• パッケージ i が スキップした、B[i][j]は容量jの下でパッケージ{1, …, i-1}を使用した最良の値に等しい。

B[i][j] = B[i - 1][j]

• パッケージ i が 撮影 (W[i] ≤ j の場合のみ許可)、B[i][j] は V[i] に容量 j – W[i] の下でパッケージ {1, …, i-1} から最良の値を加えた値に等しくなります。

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

2つの候補のうち、大きい方を選びなさい。

動的計画法の基礎

この2つのケースを組み合わせると、完全な再帰式が得られます。

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

基本ケースは B[0][j] = 0 すべての j について、容量に関係なく、パッケージがゼロの場合は値がゼロになるためです。

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

再帰を使用して B を構築します。B が満たされると、同じテーブルが次の処理を実行します。 trac選択されたパッケージを再構築するe-back。表Bはn+1行、M+1列です。

• 0行目は基本ケースであり、すべてゼロで埋められています。
• 行0を使って行1を計算し、行1を使って行2を計算し、行nが完了するまでこれを繰り返します。

オプションの表

Trace

Bが完了したら、 B[n][M]容量Mを持つn個のパッケージ全体の最適な合計値。

• If B[n][M] = B[n-1][M]パッケージ n は選択されませんでしたので、続行します tracB[n-1][M]からing。
• If B[n][M] ≠ B[n-1][M]パッケージnが選択されましたので、続行します tracB[n-1][M – W[n]]から取得します。

表の0行目に到達するまで繰り返してください。

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

注: B[i][j] = B[i-1][j]パッケージ i は選択されていません。 B[n][M] これは、ナップサックに詰め込まれる最適な合計価値です。

の手順 trac選択したパッケージを表示します:

• ステップ1： i = n、j = M から開始します。
• ステップ2： 列 j を下から上にスキャンして、B[i][j] > B[i-1][j] となる行 i が見つかるまで進めます。パッケージ i を選択済みとしてマークします。 Select[i] = true.
• ステップ3： j = j – W[i] と更新します。j > 0 の場合はステップ 2 に戻り、そうでない場合はステップ 4 に進みます。
• ステップ4： 選択済みとマークされたすべてのパッケージを印刷してください。

Java Code

以下 Java メソッドは B[][] を下から上に埋め、検査のためにテーブルを出力し、 trac選択されたパッケージを実行します。

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: ");

    int j = M;
    while (n != 0) {
        if (B[n][j] != B[n - 1][j]) {
            System.out.println("\tPackage " + n + " with W = " + W[n - 1] + " and Value = " + V[n - 1]);
            j = j - W[n - 1];
        }
        n--;
    }
}

関数knapsackDyProg() Java

コードの説明：

1. テーブルを割り当てる B[][] そして、すべてのセルを0に初期化します。
2. 前のセクションの漸化式を使用して、B[][]を下から上に埋めます。
3. 各セルを「パッケージ i をスキップ」の値で開始します。 B[i-1][j].
4. パッケージ i を選択することが可能で、かつ厳密に優れた値が得られる場合は、セルを上書きします。
5. Tracn行目から0行目まで選択した項目をeします。
6. パッケージ n が選択されるたびに、残りの容量を減算します。 W[n-1].

修正メモ： 元のスニペットの変更されたパラメータ M 読みながら B[n][M]上記のより安全なバージョンでは、別のカーソルを使用しています。 j trace.

その Java ドライバは、2つの実行例に対してアルゴリズムを実行します。

public void run() {
    // First Example
    // int W[] = new int[]{3, 4, 5, 9, 4};
    // int V[] = new int[]{3, 4, 4, 10, 4};
    // int M = 11;

    // Second Example
    int W[] = new int[]{12, 2, 1, 1, 4};
    int V[] = new int[]{4, 2, 1, 2, 10};
    int M = 15;

    int n = V.length;
    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

2番目の例の出力：

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

0/1ナップサックの時間計算量と空間計算量

• 時間計算量: O(n · M) — 2 つのネストされたループは、n 個のアイテムを M+1 個の容量状態にわたって走査します。
• 空間計算量: 完全なテーブルでは O(n · M) ですが、kee を使用することで O(M) に削減できます。ping 前の行のみ trac電子版の返却は不要です。

実行時間は 擬多項式Mの値に関しては多項式ですが、Mをエンコードするために使用されるビット数に関しては指数関数的です。そのため、動的計画法は実際には効率的であるにもかかわらず、0/1ナップサック問題はNP困難のままです。

0/1ナップサック問題の応用

• 重量制限内での貨物積載、コンテナ梱包、倉庫ピッキング。
• 固定費と期待収益を伴う投資プロジェクトへの予算配分。
• 個々の部品に分割できない製造工程における、切断在庫の問題。
• ナップサック困難性に基づいた、マークル・ヘルマン暗号方式など。
• クラウドコンピューティングにおけるリソース制約のあるスケジューリングとCPUタスク配置。
• 固定された特徴量予算の下での機械学習における特徴量選択。

よくあるご質問