Java プログラミングスキル - データ構造とアルゴリズム「動的プログラミングアルゴリズム」

[[399211]]

応用シナリオ - ナップサック問題

バックパックの問題: 容量 4 ポンドのバックパックがあり、次のアイテムが利用可能です。

目標は、バックパックの合計価値を最大化し、重量を超えないようにすることです。
ロードする必要があるアイテムは重複できません

動的プログラミングアルゴリズム入門

動的計画法アルゴリズムの中心的な考え方は、大きな問題を小さな問題に分割して解決し、段階的に最適な解決策を得ることです。
動的プログラミングアルゴリズムは、分割統治アルゴリズムに似ています。その基本的な考え方は、解決する問題をいくつかのサブ問題に分解し、最初にサブ問題を解決し、次にこれらのサブ問題の解決策から元の問題の解決策を取得することです。
分割統治アルゴリズムとは異なり、動的計画法に適用可能な問題を分解することによって得られるサブ問題は、互いに独立していないことがよくあります。 (つまり、次のサブステージの解決は、前のサブステージの解決に基づいてさらに解決されます)。
動的プログラミングは、最適な解を得るために表に記入することで徐々に進めることができます。

ナップザック問題分析

ナップザック問題とは、主に、指定された容量のナップザックと、特定の価値と重量を持ついくつかのアイテムを指します。アイテムの価値が最大になるように、ナップザックに入れるアイテムを選択する方法。 01バックパックとコンプリートバックパック（コンプリートバックパックとは、各アイテムが無制限に利用できることを意味します）に分かれています。

ここでの問題は、01 バックパックに関するものです。つまり、バックパックに入れることができるのは各アイテムを最大で 1 つだけであり、無限バックパックは 01 バックパックに変換できます。

思考分析

アルゴリズムの主なアイデアは、動的プログラミングを使用して解決することです。 i番目のアイテムが走査されるたびに、w[i]とv[i]に基づいてアイテムをバックパックに入れる必要があるかどうかが決定されます。つまり、n個のアイテムが与えられた場合、v[i]とw[i]をそれぞれi番目のアイテムの価値と重量とし、Cをバックパックの容量とします。 v[i][j]は容量jのバックパックに詰め込める最初のi個のアイテムの最大値を表すものとします。以下の結果が得られます。

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][j],v[i]+v[i-1][jw[i]]}; //追加する新しい商品の容量がバックパックの現在の容量以下の場合、ロード方法は次のとおりです: v[i-1][j]: 前のセルの最大値 v[i]: 現在の商品の値 v[i-1][jw[i]]: i-1 個の商品を残りのスペース [jw[i] の最大値までロードします

フォーム入力プロセス

コード例

パッケージ com.xie.algorithm; 
 
 java.util.Arrays をインポートします。 
 
パブリッククラスKnapsackProblem {
公共 静的void main(String[] args) {
        //アイテムの重量
整数[] w = {1, 4, 3};
        //アイテムの値
int [] 値 = {1500, 3000, 2000};
        //バックパックの容量
整数m = 4;
        //アイテム数
int n = val.length; 
 
        //商品投入状況を記録するため、2次元配列を定義する
int [][] パス = 新しいint [n + 1][m + 1]; 
 
        //2次元配列を作成する
        //v[i][j]は、容量jのバックパックに積載できる最初のi個のアイテムの最大値を表します。
 int [][] v = 新しいint [n + 1][m + 1]; 
 
        // 最初の行と列を初期化する
        // 最初の列を 0 に設定する
( int i = 0; i < v.length; i++) {
            0 = 0;
        }
        // 最初の行を 0 に設定する
( int i = 0; i < v[0].length; i++) {
            0 から 0 までの値をとる。
        } 
 
        //前の式に従った動的計画処理
        //最初の行は処理しない
( int i = 1; i < v.length; i++) {
            //最初の列は処理しない
( int j = 1; j < v[0].length; j++) {
                //式
                //プログラムiは1から始まるため、元の式のw[i]はw[i-1]に変更されます。
                (w[i - 1] > j) の場合 {
                    v[i][j] = v[i - 1][j];
                }それ以外{
                    //プログラムは1から始まるので
                    //v[i][j] = Math.max (v[i - 1][j], val[i - 1] + v[i - 1][j - w[i - 1]]);
                    (v[i - 1][j] > val[i - 1] + v[i - 1][j - w[i - 1]]) の場合 {
                        v[i][j] = v[i - 1][j];
                    }それ以外{
                        v[i][j] = val[i - 1] + v[i - 1][j - w[i - 1]];
                        //現在の状況をパスに記録する
                        パス[i][j] = 1;
                    }
                }
            }
        } 
 
 ( int i = 0; i < v.length; i++) {
            システム.out.println (Arrays.toString(v[i]));
        } 
 
 int i = パスの長さ - 1;
 int j = パス[0].長さ - 1;
        i > 0 && j > 0 の場合
            パス[i][j] == 1の場合{
                System.out.printf ( "%d番目のアイテムがバックパックに入れられました\n" 、i);
                j = w[i - 1];
            }
            私  - ;  
        }
    } 
 
    /**
     * [0, 0, 0, 0, 0, 0]
     * [0, 1500, 1500, 1500, 1500]
     * [0, 1500, 1500, 1500, 3000]
     * [0, 1500, 1500, 2000, 3500]
     * 3番目のアイテムはバックパックに入れられます
     * 最初のアイテムはバックパックに入れられます
     */
 }