Java使用動态規劃算法思想解決背包問題

背包問題是一種組合優化的NP完全問題。問題可以描述為：給定一組物品，每種物品都有自己的重量和價格，在限定的總重量内，我們如何選擇，才能使得物品的總價格最高

動态規劃算法

動态規劃算法的思想

動态規劃算法處理的對象是多階段複雜決策問題，動态規劃算法和分治算法類似，其基本思想也是将待求解問題分解成若幹個子問題(階段)，然後分别求解各個子問題(階段)，最後将子問題的解組合起來得到原問題的解，但是與分治算法不同的是，子問題往往不是互相獨立的，而是互相聯系又互相差別的

動态規劃算法問題求解的目标是擷取導緻問題最優解的最優決策序列(最優政策)。對于一個決策序列，可以用一個數值函數(目标函數)衡量這個決策的優劣。

最優性原理

動态規劃算法的最優性原理：一個最優決策序列具有這樣的性質，不論初始狀态和第一步決策如何，對前面的決策所形成的狀态而言，其餘的決策必須按照前一次決策所産生的新狀态構成一個最優決策序列。

最優性原理展現為問題的最優子結構特性，對于一個問題，如果能從較小規模的子問題的最優解求得較大規模同類子問題的最優解，最終得到給定問題的最優解，也就是問題的最優解中所包含的子問題的最優解，這種性質被稱為最優子結構性質。最優子結構特性使得在從較小問題的解構造較大問題的解時，隻需考慮子問題的最優解，然後以自底向上的方式遞歸地從子問題的最優解逐漸構造出整個問題的最優解，它保證了原問題的最優解可以通過求解子問題的最優解來獲得，最優子結構的特性是動态規劃算法求解問題的必要條件。

動态規劃算法的三大特點

• 如果求解的問題滿足最優性原理，則說明用動态規劃算法有可能解決該問題，在分析問題的最優子結構時，所使用的方法具有普遍性。要注意一個問題可以有多種方式刻畫它的最優子結構，有些表示方法的求解速度更快(空間占用少，問題的次元低)。
• 遞歸定義最優解決方案。動态規劃的每一步決策都依賴于子問題的解，動态規劃算法求解最優化問題的步驟為:找出最優解的結構，具體來說就是看這個問題是否滿足最優子結構特性；其次遞歸定義一個最優解的值，即構造原問題和子問題之間的遞歸方程，原問題的最優解可以通過子問題的最優解獲得。
• 以自底向上的方式計算出最優解的值(最優解的目标函數的值)。對子問題的分解是基于原問題的分解的基礎之上進行的，而且這些子問題的分解過程是互相獨立的。在對原問題分解的過程中，會出現大量的共享重疊子問題，為了避免對大量重疊子問題的重複計算，一般動态規劃算法從自底向上開始計算，對每一個問題隻解一次，并且儲存求解子問題的最優值，當再需要求解這個子問題的時候，可以用常數時間檢視一下結果，而不是再遞歸的去求解每一個問題的解，是以提高了動态規劃算法的效率。

動态規劃算法中的0/1背包問題

0/1背包問題的規則是不允許該物品進行拆分，即隻有把物品放入和不放入兩個基本狀态，要使用動态規劃算法求解決如何放物品才可以是背包中的物品的總價值達到最高。

示例

有一個載重為10的背包，現有4類物品，每類物品的重量分别為(w0,w1,w2,w3)=(2,3,4,7),它們的價值分别為(p0,p1,p2,p3)=(1,3,5,9)。試問如何裝載能夠使背包容納物品的價值最大。

package com.xuda.test
 import java.util.Arrays;
 import java.util.Scanner;
 //m表示的是背包的容量，a表示有多少種類的物品，數組w用與存放每類物品的重量，數組val用于存放每類物品的價值
 public class my {
     public static void main(String[] args){
         Scanner scanner = new Scanner(System.in);
         System.out.print("請輸入背包的容量:");
         int m = scanner.nextInt();
         Scanner inScanner = new Scanner(System.in);
         System.out.print("請輸入物品的個數:");
         int a = inScanner.nextInt();
         int[] w = new int[a + 1];
         System.out.print("請輸入物品的重量:" + " ");
         for (int i = 1; i <= a; i++) {
             w[i] = inScanner.nextInt();
         }
         int[] val = new int[a+ 1];
         System.out.print("請輸入物品的價值:" + " ");
         for (int i = 1; i <= a; i++) {
             val[i] = inScanner.nextInt();
         }
         int n = val.length;
         int[][] path = new int[n +1][m+1 ];
         //建立二維數組
         //v[i][j]：表示在前i個物品中能夠裝入容量為j的背包中的最大價值
         int[][] v = new int[n +1][m + 1];
         //初始化第一行和第一列
         for (int i = 0; i < v.length; i++) {//v.length:擷取二維數組的行數
             v[i][0] = 0;//将第一列設定為0
         }
         for (int i = 0; i < v[0].length; i++) {//v[0].length：擷取二維數組的列數
             v[0][i] = 0;//将第一行設定為0
         }
         for (int i = 1; i < v.length; i++) {//int i = 1 不處理第一行
             for (int j = 1; j < v[0].length; j++) {//int j = 1 不處理第一列
                 if (w[i - 1] > j) {
                     v[i][j] = v[i - 1][j];
                 } else {
                     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]];
                         //把目前情況記錄到path
                         path[i][j] = 1;
                     } else {
                         v[i][j] = v[i - 1][j];
                     }
                 }
             }
         }
         //輸出二維數組：
         for (int[] ints : v) {
             System.out.println(Arrays.toString(ints));
         }
         //輸出最後我們是放入的那些商品
         int i = path.length - 1;//行的最大下标
         int j = path[0].length - 1;//列的最大下标
         while (i > 0 && j > 0) {//從path的最後開始找
             if (path[i][j] == 1) {
                 System.out.printf("第%d個商品放入背包\n", i-1);
                 j -= w[i - 1];
             }
             i--;
         }
     }
 }
      

輸入一個背包容量為10，裡面有4類物品，物品的重量分别為2，3，4，7，物品的價值分别為1，3，5，9

動态規劃算法的優點