動態(tài)規(guī)劃：

所有的數(shù)據(jù)結(jié)構(gòu)與算法的理解必須建立在題目的練習(xí)上，否則看多少理論都沒有實際用處！！！

所以下面這些理論文字看不懂通通沒關(guān)系，跟隨下面的背包問題還會跟深入的理解。

一、基本概念：任何數(shù)學(xué)遞推公式都可以直接轉(zhuǎn)換成遞歸算法，但是基本現(xiàn)實是編譯器常常不能正確對待遞歸算法，結(jié)果導(dǎo)致低效的程序。當(dāng)懷疑很可能是這種情況是，我們必須給編譯器提供一些幫助，將遞歸算法重新寫成非遞歸算法讓后者把這些子問題的答案系統(tǒng)地記錄在一個表內(nèi)。利用這種方法的一種技巧叫做動態(tài)規(guī)劃。根據(jù)《數(shù)據(jù)結(jié)構(gòu)與算法分析--Java語言描述》原書第三版?中給動態(tài)規(guī)劃（DP）的定義（出自《數(shù)據(jù)結(jié)構(gòu)與算法分析--Java語言描述》原書第三版?）

二、主要分類：動態(tài)規(guī)劃一般可分為線性動規(guī)，區(qū)域動規(guī)，樹形動規(guī)，背包動規(guī)四類。
舉例：
線性動規(guī)：攔截導(dǎo)彈，合唱隊形，挖地雷，建學(xué)校，劍客決斗等；
區(qū)域動規(guī)：石子合并， 加分二叉樹，統(tǒng)計單詞個數(shù)，炮兵布陣等；
樹形動規(guī)：貪吃的九頭龍，二分查找樹，聚會的歡樂，數(shù)字三角形等；
背包動規(guī)：01背包問題，完全背包問題，分組背包問題，二維背包，裝箱問題，擠牛奶等；
除此之外還有許多變形的動態(tài)規(guī)劃問題，再次不一一列舉。

三、動態(tài)規(guī)劃問題中的術(shù)語（這一部分看不懂沒關(guān)系，用處不大）

階段：把所給求解問題的過程恰當(dāng)?shù)胤殖扇舾蓚€相互聯(lián)系的階段，以便于求解，過程不同，階段數(shù)就可能不同。描述階段的變量稱為階段變量。
狀態(tài)：狀態(tài)表示每個階段開始面臨的自然狀況或客觀條件，它不以人們的主觀意志為轉(zhuǎn)移，也稱為不可控因素。在具體題目中，狀態(tài)就是某階段的出發(fā)位置，它既是該階段某路的起點，同時又是前一階段某支路的終點。
無后效性：我們要求狀態(tài)具有下面的性質(zhì)：如果給定某一階段的狀態(tài)，則在這一階段以后過程的發(fā)展不受這階段以前各段狀態(tài)的影響，所有各階段都確定時，整個過程也就確定了。狀態(tài)的這個性質(zhì)意味著過程的歷史只能通過當(dāng)前的狀態(tài)去影響它的未來的發(fā)展。
決策：一個階段的狀態(tài)給定以后，從該狀態(tài)演變到下一階段某個狀態(tài)的一種選擇（行動）稱為決策。在最優(yōu)控制中，也稱為控制。因狀態(tài)滿足無后效性，故在每個階段選擇決策時只需考慮當(dāng)前的狀態(tài)而無須考慮過程的歷史。
策略：由每個階段的決策組成的序列稱為策略。集合中達(dá)到最優(yōu)效果的策略稱為最優(yōu)策略。

最優(yōu)化原理:作為整個過程的最優(yōu)策略，它滿足：相對前面決策所形成的狀態(tài)而言，余下的子策略必然構(gòu)成“最優(yōu)子策略”。一個問題滿足最優(yōu)化原理也稱其擁有最優(yōu)子結(jié)構(gòu)性質(zhì)。最優(yōu)性原理實際上是要求問題的最優(yōu)策略的子策略也是最優(yōu)。

四、基本思想：動態(tài)規(guī)劃思想通常用于求解具有某種最優(yōu)性質(zhì)的問題。在這類問題中，可能會有許多可行解。其基本思想也是將待求解問題分解成若干個子問題，先求解子問題，然后從這些子問題的解得到原問題的解。但是適合于用動態(tài)規(guī)劃求解的問題，經(jīng)分解得到子問題往往不是互相獨立的。如果我們能夠保存已解決的子問題的答案，而在需要時再找出已求得的答案，這樣就可以避免大量的重復(fù)計算。我們可以用一個表來記錄所有已解的子問題的答案。不管該子問題以后是否被用到，只要它被計算過，就將其結(jié)果填入表中。

五、解題思路：

1.找出最優(yōu)解的性質(zhì)，刻畫其結(jié)構(gòu)特征和最優(yōu)子結(jié)構(gòu)特征；
2.遞歸地定義最優(yōu)值，刻畫原問題解與子問題解間的關(guān)系，找到狀態(tài)方程；
3.以自底向上的方式計算出各個子問題最優(yōu)解，并避免子問題的重復(fù)計算；
4.根據(jù)計算最優(yōu)值時得到的信息，構(gòu)造最優(yōu)解。

01背包

問題描述：

有N件物品和一個容量為C的背包。第i件物品的體積是v[i]，價值是w[i]。求解將哪些物品裝入背包可使價值總和最大。

?從這個題目中可以看出，01背包的特點就是：每種物品僅有一件，可以選擇放或不放。

輸入：第一行兩個數(shù)據(jù)，物品件數(shù)N，背包容量C

接下來N行，每行對應(yīng)第i件物品的體積v[i]和價值w[i]

Input：

3 9

1 2

2 3

3 1

Output：

6

思路一：逆向規(guī)劃

我們假定當(dāng)前階段的狀態(tài)d(i, j)表示當(dāng)前第i層，將從第i個到第n個物品裝入容量為j的背包所能達(dá)到的最大重量

由此，規(guī)劃的終點就是d(1, c)[即代表將第1，2,3，...，n個物品裝入容量為G的背包中所能達(dá)到的最大重量]

規(guī)劃的起點就是d(n, 0) 或 d(n, c)

如果我們不放物品i，狀態(tài)轉(zhuǎn)移為d(i+1, j)，即將物品i+1放入剩余容量仍為j的背包中的價值

如果我們放入物品i，狀態(tài)轉(zhuǎn)移為d(i+1, j-v[i])+w[i], 即將物品i+1放入剩余容量為j-v[i]的背包中的價值

狀態(tài)轉(zhuǎn)移方程：d(i, j) = max{d(i+1, j), d(i+1, j-v[i]) + w[i]}

import java.util.Scanner;public class Main {static Scanner in = new Scanner(System.in);static int[] v,w;static int[][] d;static int n, c;public static void main(String[] args) {n = in.nextInt();c = in.nextInt();v = new int[n+1];w = new int[n+1];d = new int[n+2][c+1];for (int i = 1; i <= n; i++) {v[i] = in.nextInt();w[i] = in.nextInt();}for(int i = n; i >= 1; i--) {for(int j = 0; j <= c; j++) {d[i][j] = (i==n ? 0 : d[i+1][j]);if(j >= v[i]) {d[i][j] = Math.max(d[i][j],d[i+1][j-v[i]]+w[i]);}}}System.out.println(d[1][c]);} }

思路二：正向規(guī)劃

我們假定當(dāng)前階段的狀態(tài)d(i, j)表示當(dāng)前第i層，將前i個物品裝入容量為j的背包所能達(dá)到的最大重量

規(guī)劃的起點d(1, 0) 或 d(1, c)

規(guī)劃的終點d(n ,c)

狀態(tài)轉(zhuǎn)移方程：d(i, j) = max{d(i-1, j), d(i-1, j-v[i]) + w[i]}

import java.util.Scanner;public class Main {static Scanner in = new Scanner(System.in);static int[] v,w;static int[][] d;static int n, c;public static void main(String[] args) {n = in.nextInt();c = in.nextInt();v = new int[n+1];w = new int[n+1];d = new int[n+1][c+1];for(int i = 1; i <= n; i++) {int v = in.nextInt();int w = in.nextInt();for(int j = 0; j <= c; j++) {d[i][j] = (i==1 ? 0 : d[i-1][j]);if(j >= v) {d[i][j] = Math.max(d[i][j],d[i-1][j-v]+w);}}}System.out.println(d[n][c]);} } 思路一與思路二區(qū)別： 1. 正向規(guī)劃可以在輸入v, w的過程中處理數(shù)據(jù)，節(jié)省空間；在打印結(jié)果的時候不方便 2. 逆向規(guī)劃可以保證打印結(jié)果時最小字典序；需要存儲v, w



下面引入一個概念 滾動數(shù)組：形態(tài)上是一個一維數(shù)組，其作用在于可以優(yōu)化空間，主要應(yīng)用在遞推或動態(tài)規(guī)劃中（尤其是在背包問題中）。 由于DP題目是一個自底向上的擴(kuò)展過程，我們常常需要用到的是連續(xù)的解，當(dāng)一個狀態(tài)轉(zhuǎn)移到另一個狀態(tài)時，大多數(shù)情況下，之前存儲的狀態(tài)信息已經(jīng)無用了，往往可以舍去。所以用滾動數(shù)組優(yōu)化是很有效的。 好處：利用滾動數(shù)組可以在N很大的情況下達(dá)到壓縮存儲的作用。滾動數(shù)組在時間上并沒有什么改善，但是能節(jié)省很大的空間。 不足：由于沒有存儲之前的數(shù)據(jù)，所以在實現(xiàn)打印方面十分困難

思路三：用滾動數(shù)組實現(xiàn)

我們假定當(dāng)前階段的狀態(tài)d(j)表示將當(dāng)前物品裝入容量為 j 的背包所能達(dá)到的最大重量

規(guī)劃的起點d( 0 )

規(guī)劃的終點d( c )

狀態(tài)轉(zhuǎn)移方程：d( j ) = max{d( j ), d( j - v) + w}

import java.util.Scanner;public class Main {static Scanner in = new Scanner(System.in);static int[] v, w, d;static int n, c;public static void main(String[] args) {n = in.nextInt();c = in.nextInt();v = new int[n+1];w = new int[n+1];d = new int[c+1];for (int i = 1; i <= n; i++) {int v = in.nextInt();int w = in.nextInt();for (int j = c; j >= 0; j--) {if (j >= v) {d[j] = Math.max(d[j], d[j-v] + w);}}}System.out.println(d[c]);} }
注意：

在這類求最優(yōu)解的背包問題中，有的題目要求“恰好裝滿背包”時的最優(yōu)解，而有的題目則并沒有要求必須裝滿。

區(qū)別這兩種問法的實現(xiàn)方法是在初始化的時候有所不同。

如果是要求恰好裝滿背包，那么在初始化時除了f[0]為0其它f[1..V]均設(shè)為-∞，這樣就可以保證最終得到的f[N]是一種恰好裝滿背包的最優(yōu)解。

如果并沒有要求必須把背包裝滿，而是只希望價格盡量大，初始化時應(yīng)該將 f[0..V]全部設(shè)為0。

為什么呢？可以這樣理解：初始化的f數(shù)組事實上就是在沒有任何物品可以放入背包時的合法狀態(tài)。如果要求背包恰好裝滿，那么初始化時只有容量為0的背包可能被價值為0的物品“恰好裝滿”，其它容量的背包尚且沒有合法的解，屬于未定義的狀態(tài)；如果背包并非必須被裝滿，那么初始化時任何容量的背包都有一個合法解，即什么都不裝。

總結(jié)

以上是生活随笔為你收集整理的从背包问题优化详解动态规划思想的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。