アルゴリズム問題のダイナミックプランニング-01リュックサック問題

リュックサックの問題を解決する文字紹介
洞窟にa,b,c,d,eという5つの宝物(5つの宝物ではない)があると仮定します.それらの重さはそれぞれ2,2,6,5,4で、それらの価値はそれぞれ6,3,5,4,6で、今あなたに重さ10のリュックサックをあげて、どのようにリュックサックを入れて、最も多くの富を持っていくことができます.
このとき,状態変換方程式f[i,j]=Max{f[i−1,j−wi]+Pi(j>=Wi),f[i−1,j]}を理解すれば,このアルゴリズムの答えが分かるが,この状態変換方程式はどのように来ているのだろうか.下を見る

       i   ，       i   ，        “ i-1        w    ”，   f[i-1,j]；
    i   ，        “ i-1           j-Wi    ”，            f[i-1,j-Wi]
        i        Pi，      f[i-1,j] f[i-1,j-Wi]+Pi                    。

まだよく分からないかもしれませんが、図を見て理解しましょう.ここでは大物の写真を使っています.次の写真です.番号がa,b,c,d,eの5つのものがあります.それらの重さはそれぞれ2,2,6,5,4で、それらの価値はそれぞれ6,3,5,4,6です.今、重さが10のリュックサックをあげます.どうやって価値の最大のリュックサックを手に入れますか.
まずこの画像について知りたいのは、

は、このテーブルが左から右にかけて生成されたことを明らかにした.

それからe 2のセルでe行の2列のセルを表して、このセルの意味は物品eだけを表す時、重さが2のリュックサックがあって、それではこのリュックサックの最大の価値は0で、eの物品の重さが4なので、リュックサックは入れられません.

はd 2セルに対して、物品e,dのみを表す場合、荷重が2のリュックサックであり、入れることができる最大の価値は、依然として0である.物品e,dはこのリュックサックに入れられるものではないからである.

同理,c 2=0,b 2=3,a 2=6.

重さ8のリュックサックに対して、a 8=15は、どのようにして得られたのでしょうか.01リュックの状態変換方程式によれば,2つの値を考察する必要があり,以下の2つである.

は1つがf[i-1,j]であり、この場合は荷重8のリュックの中にaというものが入っていない場合(上の状態変換方程式から来ている)であり、ここでiは下の横列の値、そしてjは縦列の値を指すので、このときf[i-1,j]の中のiはa,jは8であり、aの次の列はbであるため、f[i-1,j]はb 8を指す.このときのf[i-1,j]の値は9

である.

もう一つはf[i-1,j-wi]+Piで、この場合は荷重8のリュックの中にaというものを入れる場合(上の状態変換方程式に基づいて)、aというものを入れる以上、この場合のPiの値は6(a商品の価値は6)であり、荷重8のリュックの中にaというものを入れることが確定しているため、このときこのリュックサックの中で最大6しか保管できない重量は、ここでiは下の横列の値、そしてjは縦列の値を指すので、このときf[i-1,j-Wi]の中のiはa、jは8、Wiは2(この2はa物の重量)なので、このときf[i-1,j-Wi]はb 6を指し、このときb 6の値は9なので、f[i-1,j-Wi]+Pi=9+6=15、だから品物aは重さが8のリュックサックの中に入れるべきです

JAvaコードこのリュックサックの問題を解く
次の赤いコード注釈の中の配列の中の最初のインデックスはすべて0で、これは配列の0インデックスの問題を避けるためです
次の青いコードの注釈の中のforループの目的はこのような画像を作成するためで、それから上の画像を作成すれば、リュックサックの問題の答えを知ることができます

package com.one.util;

public class Test {
    public static int getMaxValue(int[] weight, int[] value, int w, int n) {
        int[][] table = new int[n + 1][w + 1];//         ，        ，        
        //         
        for (int i = 1; i <= n; i++) { //  
            for (int j = 1; j <= w; j++) {  //    
                if (weight[i] > j) {
                    //    i        j ，   ，      
                    table[i][j] = table[i - 1][j];
                } else { //   ，Max{   i，     i}
                    table[i][j] = Math.max(table[i - 1][j], table[i - 1][j - weight[i]] + value[i]);
                }
            }
        }
        //         
        return table[n][w];
    }

    public static void main(String[] args) {
        int n = 5, w = 10;                    //    ，    
        //         
        int[] value = {0,6, 3, 5, 4, 6};     //       
        int[] weight = {0,2, 2, 6, 5, 4};    //       
        //         
        System.out.println(getMaxValue(weight, value, w, n));
    }
}

大男のウェブサイトhttps://blog.csdn.net/evillist/article/details/74455044 https://www.kancloud.cn/kancloud/pack/70125 https://blog.csdn.net/mu399/article/details/7722810