快捷導(dǎo)航

Java使用動態(tài)規(guī)劃算法思想解決背包問題

更新時(shí)間：2022年04月29日 10:05:46 作者：LNORA

背包問題(Knapsack problem)是一種組合優(yōu)化的NP完全問題。問題可以描述為：給定一組物品，每種物品都有自己的重量和價(jià)格，在限定的總重量內(nèi)，我們?nèi)绾芜x擇，才能使得物品的總價(jià)格最高

動態(tài)規(guī)劃算法

動態(tài)規(guī)劃算法的思想

動態(tài)規(guī)劃算法處理的對象是多階段復(fù)雜決策問題，動態(tài)規(guī)劃算法和分治算法類似，其基本思想也是將待求解問題分解成若干個(gè)子問題(階段)，然后分別求解各個(gè)子問題(階段)，最后將子問題的解組合起來得到原問題的解，但是與分治算法不同的是，子問題往往不是相互獨(dú)立的，而是相互聯(lián)系又相互區(qū)別的

動態(tài)規(guī)劃算法問題求解的目標(biāo)是獲取導(dǎo)致問題最優(yōu)解的最優(yōu)決策序列(最優(yōu)策略)。對于一個(gè)決策序列，可以用一個(gè)數(shù)值函數(shù)(目標(biāo)函數(shù))衡量這個(gè)決策的優(yōu)劣。

最優(yōu)性原理

動態(tài)規(guī)劃算法的最優(yōu)性原理：一個(gè)最優(yōu)決策序列具有這樣的性質(zhì)，不論初始狀態(tài)和第一步?jīng)Q策如何，對前面的決策所形成的狀態(tài)而言，其余的決策必須按照前一次決策所產(chǎn)生的新狀態(tài)構(gòu)成一個(gè)最優(yōu)決策序列。

最優(yōu)性原理體現(xiàn)為問題的最優(yōu)子結(jié)構(gòu)特性，對于一個(gè)問題，如果能從較小規(guī)模的子問題的最優(yōu)解求得較大規(guī)模同類子問題的最優(yōu)解，最終得到給定問題的最優(yōu)解，也就是問題的最優(yōu)解中所包含的子問題的最優(yōu)解，這種性質(zhì)被稱為最優(yōu)子結(jié)構(gòu)性質(zhì)。最優(yōu)子結(jié)構(gòu)特性使得在從較小問題的解構(gòu)造較大問題的解時(shí)，只需考慮子問題的最優(yōu)解，然后以自底向上的方式遞歸地從子問題的最優(yōu)解逐步構(gòu)造出整個(gè)問題的最優(yōu)解，它保證了原問題的最優(yōu)解可以通過求解子問題的最優(yōu)解來獲得，最優(yōu)子結(jié)構(gòu)的特性是動態(tài)規(guī)劃算法求解問題的必要條件。

動態(tài)規(guī)劃算法的三大特點(diǎn)

如果求解的問題滿足最優(yōu)性原理，則說明用動態(tài)規(guī)劃算法有可能解決該問題，在分析問題的最優(yōu)子結(jié)構(gòu)時(shí)，所使用的方法具有普遍性。要注意一個(gè)問題可以有多種方式刻畫它的最優(yōu)子結(jié)構(gòu)，有些表示方法的求解速度更快(空間占用少，問題的維度低)。
遞歸定義最優(yōu)解決方案。動態(tài)規(guī)劃的每一步?jīng)Q策都依賴于子問題的解，動態(tài)規(guī)劃算法求解最優(yōu)化問題的步驟為:找出最優(yōu)解的結(jié)構(gòu)，具體來說就是看這個(gè)問題是否滿足最優(yōu)子結(jié)構(gòu)特性；其次遞歸定義一個(gè)最優(yōu)解的值，即構(gòu)造原問題和子問題之間的遞歸方程，原問題的最優(yōu)解可以通過子問題的最優(yōu)解獲得。
以自底向上的方式計(jì)算出最優(yōu)解的值(最優(yōu)解的目標(biāo)函數(shù)的值)。對子問題的分解是基于原問題的分解的基礎(chǔ)之上進(jìn)行的，而且這些子問題的分解過程是相互獨(dú)立的。在對原問題分解的過程中，會出現(xiàn)大量的共享重疊子問題，為了避免對大量重疊子問題的重復(fù)計(jì)算，一般動態(tài)規(guī)劃算法從自底向上開始計(jì)算，對每一個(gè)問題只解一次，并且保存求解子問題的最優(yōu)值，當(dāng)再需要求解這個(gè)子問題的時(shí)候，可以用常數(shù)時(shí)間查看一下結(jié)果，而不是再遞歸的去求解每一個(gè)問題的解，因此提高了動態(tài)規(guī)劃算法的效率。

動態(tài)規(guī)劃算法中的0/1背包問題

0/1背包問題的規(guī)則是不允許該物品進(jìn)行拆分，即只有把物品放入和不放入兩個(gè)基本狀態(tài)，要使用動態(tài)規(guī)劃算法求解決如何放物品才可以是背包中的物品的總價(jià)值達(dá)到最高。

示例

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

package 算法設(shè)計(jì)與分析;
 import java.util.Arrays;
 import java.util.Scanner;
 //m表示的是背包的容量，a表示有多少種類的物品，數(shù)組w用與存放每類物品的重量，數(shù)組val用于存放每類物品的價(jià)值
 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("請輸入物品的個(gè)數(shù):");
         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("請輸入物品的價(jià)值:" + " ");
         for (int i = 1; i <= a; i++) {
             val[i] = inScanner.nextInt();
         }
         int n = val.length;
         int[][] path = new int[n +1][m+1 ];
         //創(chuàng)建二維數(shù)組
         //v[i][j]：表示在前i個(gè)物品中能夠裝入容量為j的背包中的最大價(jià)值
         int[][] v = new int[n +1][m + 1];
         //初始化第一行和第一列
         for (int i = 0; i < v.length; i++) {//v.length:獲取二維數(shù)組的行數(shù)
             v[i][0] = 0;//將第一列設(shè)置為0
         }
         for (int i = 0; i < v[0].length; i++) {//v[0].length：獲取二維數(shù)組的列數(shù)
             v[0][i] = 0;//將第一行設(shè)置為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]];
                         //把當(dāng)前情況記錄到path
                         path[i][j] = 1;
                     } else {
                         v[i][j] = v[i - 1][j];
                     }
                 }
             }
         }
         //輸出二維數(shù)組：
         for (int[] ints : v) {
             System.out.println(Arrays.toString(ints));
         }
         //輸出最后我們是放入的那些商品
         int i = path.length - 1;//行的最大下標(biāo)
         int j = path[0].length - 1;//列的最大下標(biāo)
         while (i > 0 && j > 0) {//從path的最后開始找
             if (path[i][j] == 1) {
                 System.out.printf("第%d個(gè)商品放入背包\n", i-1);
                 j -= w[i - 1];
             }
             i--;
         }
     }
 }

輸入一個(gè)背包容量為10，里面有4類物品，物品的重量分別為2，3，4，7，物品的價(jià)值分別為1，3，5，9

結(jié)果

動態(tài)規(guī)劃算法的優(yōu)點(diǎn)

若要解一個(gè)給定問題，我們需要解其不同部分（即子問題），再合并子問題的解以得出原問題的解。通常許多子問題非常相似，為此動態(tài)規(guī)劃法試圖僅僅解決每個(gè)子問題一次，從而減少計(jì)算量：一旦某個(gè)給定子問題的解已經(jīng)算出，則將其記憶化存儲，以便下次需要同一個(gè)子問題解之時(shí)直接查表。這種做法在重復(fù)子問題的數(shù)目關(guān)于輸入的規(guī)模呈指數(shù)增長時(shí)特別有用。