動態規劃算法

• 動態規劃算法介紹
  • 動態規劃(Dynamic Programming)算法的核心思想是：將大問題劃分為小問題進行解決，從而一步步獲取最優解的處理算法
  • 動態規劃算法與分治法類似，其基本思想也是將待解決問題分解成若干個子問題，先求解子問題，然后從這些子問題的解得到原問題的解
  • 與分治法不同的是，適合于動態規劃求解的問題。經分解得到子問題往往不是互相獨立的。（即下一個子階段的求解是建立在上一個子階段的基礎上，進行進一步的求解）
  • 動態規劃可以通過填表的方式來逐步推進，得到最優解
• 應用場景-背包問題
  • 背包問題：有一個背包，容量為4磅，現有如下物品

    物品	重量	價格
    吉他(G)	1	1500
    音響(S)	4	3000
    電腦(L)	3	2000

    • 要求達到的目標為裝入背包的總價值最大，并且重量不超出
    • 要求裝入的物品不能重復
  • 思路分析與圖解
    • 背包問題主要是指一個給定容量的背包、若干具有一定價值和重量的物品，如何選擇物品放入背包使物品的價值最大。其中又分為01背包和完全背包（完全背包指的是：每種物品都有無限件可用）
    • 這里的問題屬于01背包，即每個物品最多放一個。而無線背包可以轉化為01背包
    • 算法的主要思想是，利用動態規劃來解決。每次遍歷到的第i個物品，根據w[i]和v[i]來確定是否需要將該物品放入背包中。即對于給定的n個物品，設v[i]、w[i]分別為第i個物品的價值和重量，C為背包的容量。再令v[i][j]表示再前i個物品中能夠裝入容量為j的背包中的最大價值。則我們得到如下結果

    1. v[i][0]=v[0][j]=0;//表示填入表第一行和第一列是0
    2. 當w[i]>j時：v[i][j]=v[i-1][j] // 當準備加入新增的商品容量大于當前背包的容量時，就直接使用上一個單元格的裝入策略
    3. 當j>=w[i]時，v[i][j]=max{v[i-1][j],v[i]+v[i-1][j-w[i]]}
    // 當準備加入的新增的商品的容量小于等于當前背包的容量
    // 裝入的方式
    v[i-1][j]：指上一個單元格裝入的最大值
    v[i]：當前商品的價值
    v[i-1][j-w[i]]：裝入i-1商品，到剩余空間j-w[i]的最大值
    

    • 圖解
      
  • 代碼實現

  public class KnapsackProblem {public static void main(String[] args) {int[] w = {1,4,3}; // 物品的重量int val[] = {1500,3000,2000}; // 物品的價值int m = 4; // 背包的容量int n = w.length; // 物品的個數// v[i][j]表示在前j個物品中能夠裝入容量為j的背包中的最大價值int[][] v = new int[n+1][m+1];// 記錄有沒有放入對應的商品.1表示放入了int[][] path = new int[n+1][m+1];// 初始化第一行和第一列，在本程序中可以不處理，因為默認是0// 根據前面得到公式來動態規劃處理// 跳過第一行和第一列for(int i = 1; i < v.length;i++) {for(int j = 1; j < v[0].length;j++) {// 當前物品大于背包容量if(w[i-1] > j) {v[i][j] = v[i-1][j];}else {// 當前物品大于等于背包容量int newValue = val[i - 1] + v[i - 1][j - w[i - 1]];if(v[i - 1][j] < newValue) {v[i][j] = newValue;// 表明把當前商品放入到背包中path[i][j] = 1;}else {v[i][j] = v[i - 1][j];}}}}// 輸出以下，看看目前的情況for (int i = 0; i < v.length; i++) {for (int j = 0; j < v[i].length; j++) {System.out.print(v[i][j] + "  ");}System.out.println();}System.out.println("------------------");// 輸出最后我們放入的是那些商品int i = path.length - 1; // 最后一個商品int j = path[0].length - 1;while(i > 0 && j > 0) {if(path[i][j] == 1) {System.out.println("把商品" + i + "放入背包中");j -= w[i-1];}i--;}}
  }