總目錄：地址如下看總綱

http://www.reibang.com/p/929ca9e209e8

1惋嚎、動態(tài)規(guī)劃算法介紹

1继找、動態(tài)規(guī)劃(Dynamic Programming)算法的核心思想是：將大問題劃分為小問題進行解決，從而一步步獲取最優(yōu)解的處理算法

2袱结、動態(tài)規(guī)劃算法與分治算法類似，其基本思想也是將待求解問題分解成若干個子問題箍镜，先求解子問題剥懒，然后從這些子問題的解得到原問題的解虫溜。

3、與分治法不同的是，適合于用動態(tài)規(guī)劃求解的問題耐朴，經(jīng)分解得到子問題往往不是互相獨立的借卧。 ( 即下一個子階段的求解是建立在上一個子階段的解的基礎(chǔ)上，進行進一步的求解 )

4筛峭、動態(tài)規(guī)劃可以通過 填表 的方式來逐步推進铐刘，得到最優(yōu)解

2、動態(tài)規(guī)劃算法最佳實踐-背包問題

有一個背包影晓，容量為4磅 镰吵， 現(xiàn)有如下物品

image.png

要求：
1、要求達到的目標為裝入的背包的總價值最大挂签，并且重量不超出
2疤祭、要求裝入的物品不能重復

3、思路分析（文字說明）

1饵婆、背包問題主要是指一個給定容量的背包勺馆、若干具有一定價值和重量的物品，如何選擇物品放入背包使物品的價值最大侨核。
2谓传、其中問題分兩種，01背包 和 完全背包(完全背包指的是：每種物品都有無限件可用)
3芹关、這里的問題屬于01背包续挟，即每種類物品最多放一個。而無限背包可以轉(zhuǎn)化為01背包侥衬。
4诗祸、算法的主要思想，利用動態(tài)規(guī)劃來解決轴总。每次遍歷到的第i個物品直颅，根據(jù) w[i] 和 v[i] 來確定是否需要將該物品放入背包中。v[i][j] 表示在前 i 個物品中能夠裝入容量為 j 的背包中的最大價值怀樟，公式和解釋如下：
（1） w[i] 表示 第 i 個商品的重量功偿， v[i] 表示 第 i 個商品的價值(價格) ，j 表示 當前背包的容量
（2） v[i][0] = v[0][j] =0; //表示 填入表 第一行和第一列是0
（3） 當w[i]> j 時：v[i][j] = v[i-1][j] ; // 當準備加入新增的商品的容量大于 當前背包的容量時往堡，就直接使用上一個單元格的裝入策略 (阿K解釋：就是現(xiàn)在月薪很低的你買不起貴的械荷，你只能買得起和上個月月薪一樣的東西...)
（4） 當 j>=w[i] 時： v[i][j] = max{v[i-1][j], v[i]+v[i-1][j-w[i]]} ; // 當 準備加入的新增的商品的容量小于等于當前背包的容量（其中max 內(nèi)的參數(shù)分兩個 ，比較出最大的一個 虑灰，賦值 給 v[i][j]）,具體解釋：
v[i-1][ j ] ： 既上一個單元格的裝入的最大值（已有的值）
v[ i - 1 ] [ j - w[ i ] ] ： 裝入i-1商品吨瞎，到剩余空間為 j-w[i] 的最大值
注：此二位數(shù)組可以看成 x軸和 y 軸， v[y] [x] 或者 v[i] [j]穆咐，以后表格對應颤诀，x軸對應的是 重量(容量)字旭，y軸則是 物品編號

背包問題填表

4、思路分析（圖分解）

（1）背包問題：有一個背包崖叫，容量為4磅 遗淳， 現(xiàn)有如下物品，
要求達到的目標為裝入的背包的總價值最大心傀，并且重量不超出洲脂。

價格表

（2）解決類似的問題可以分解成一個個的小問題進行解決，假設存在背包容量大小分為1剧包，2恐锦，3，4的各種容量的背包(分配容量的規(guī)則為最小重量的整數(shù)倍)：

image.png

image.png

image.png

（5）第三次填表：對于第三行(i=3),目前存在吉他和音響一铅、電腦可以選擇,所以

image.png

1. 案例一：v[1][1] = ? ，已知 ： w[1] = 1 堕油， j = 1 （已知數(shù)據(jù)從價格表中獲得）
   v[i][j]=max{v[i-1][j],v[i-1][j-w[i]]+v[i]} = v[1][1] = max{v[0][1], v[0][0]+v[1]} = max{0, 0 + 1500}潘飘，其中v[1]是第一件物品 吉他的價格
2. 案例二：v[3][4] = ? ，已知： w[3] = 3 掉缺， j >= w[3] （已知數(shù)據(jù)從價格表中獲得）
   v[i][j]=max{v[i-1][j],v[i-1][j-w[i]]+v[i]} = v[3][4] = max{v[2][4],v[2][1]+v[3] = max{3000,1500+3000}卜录，其中v[1]是第三件物品 電腦的價格

★注意：看表格的時候，記得物品是3 件眶明，默認添加一件 不存在的 艰毒，角標從0開始，總的是 4件(3+1)搜囱，數(shù)組角標 0 到 3 丑瞧，歸屬 y（i） 軸坐標 v[ y] [ x ] ；容量(重量) 是 4 磅(個單位)蜀肘，默認一個單位不存在绊汹，角標從 0開始， 總的是 5 件(4 + 1)扮宠，數(shù)組角標 0 到 4 西乖，歸屬 x（j）軸，坐標 v[ y ] [ x] 坛增。

5获雕、代碼

package com.kk.algorithm.dynamic;
/*
 * @Description:    動態(tài)規(guī)劃(背包問題)
 * @Author:         Jk_kang
 * @CreateDate:     2021/2/5 0:25
 * @Param:
 * @Return:
**/
public class KnapsackProblem {
    public static void main(String[] args) {

        // 物品的重量
        int[] w = {1, 4, 3};
        // 物品的單價(價值)，此處的val[i] 既 v[i] ,某個物品的單價
        int[] val = {1500, 3000, 2000};
        // 背包容量(總的或者部分)轿偎，因為它是可變的典鸡，代碼中體現(xiàn)
        int m = 4;
        // 物品個數(shù)
        int n = w.length;


        // 構(gòu)建二位數(shù)組(表格)
        // v[i][j] 表示在第i個物品中能夠裝入容量為j的背包中的最大價值
        int[][] v = new int[n + 1][m + 1];
        // 為了記錄放入商品的情況被廓，我們定一個二維數(shù)組
        int[][] table = new int[n + 1][m + 1];

        // 初始第一行坏晦，第一列，默認為 0 可以不設置，但是我愿意昆婿！
        for (int i = 0; i < v.length; i++) {
            // 初始第一列
            v[i][0] = 0;
        }
        for (int i = 0; i < v[0].length; i++) {
            // 初始第一列
            v[0][i] = 0;
        }

        // 根據(jù)思路球碉，進行動態(tài)規(guī)劃實現(xiàn)
        for (int i = 1; i < v.length; i++) {// 第一行不處理，因為默認為0
            for (int j = 1; j < v[0].length; j++) {// 第一列不處理仓蛆，因為默認為0
                // 公式 w[i] > j 實現(xiàn)
                if (w[i - 1] > j) {// 因為 從1 開始睁冬，因此公式 w[i] 需改為 w[i-1]
                    v[i][j] = v[i - 1][j];
                } else {
                    // 故因：i 從 1 開始，公式做調(diào)整
                    // 原公式：v[i][j] = Math.max (v[i - 1][j], v[i] + v[i - 1][j - w[i]]);
                    // 修改為：v[i][j] = Math.max (v[i - 1][j], val[i - 1] + v[i - 1][j - w[i - 1]]);
                    // val[] 中 -1 因為數(shù)組從 0 開始看疙，這邊循環(huán)直接從 1 開始所以 -1豆拨；
                    // w[] 中 -1 也同上理

                    //為了記錄商品存放到背包的情況，我們不能直接的使用上面的公式能庆，需要使用if-else來體現(xiàn)公式
                    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]];
                        // 則把情況記錄
                        table[i][j] = 1;// 記錄當前坐標為最優(yōu)，用狀態(tài) 1 表示
                    } else {
                        // 若新增不是最優(yōu)搁胆，就和上個單元格一致
                        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] + "\t");
            }
            System.out.println ( );
        }

        //錯誤輸出, 這樣輸出會把所有的放入情況都得到, 其實我們只需要最后的放入
//      for(int i = 0; i < table.length; i++) {
//          for(int j=0; j < table[i].length; j++) {
//              if(table[i][j] == 1) {
//                  System.out.printf("第%d個商品放入到背包\n", i);
//              }
//          }
//      }

        //正確輸出：逆向輸出最后一個商品的 排列順序
        int i = table.length - 1; //行的最大下標
        int j = table[0].length - 1;  //列的最大下標
        while(i > 0 && j > 0 ) { //從table 的最后開始找
            if(table[i][j] == 1) {// 坐標滿足最優(yōu)
                System.out.printf("第%d個商品放入到背包\n", i);
                j -= w[i-1]; //w[i-1]弥搞，查找一個物品后 減去對應的重量
            }
            i--;// 查找一個物品后 -1
        }
    }
}

6、坐標

image.png