1.定義

動態規劃：把多階段過程轉化為一系列單階段問題，利用各階段之間的關系，逐個求解。

?

2.求解步驟

（1）找到狀態轉化條件

（2）歸納狀態轉移方程

（3）定義初始條件值

?

3.實例解析——0/1背包問題

? ?有n個物品，每個物品容量w[i]不同，對應的價值v[i]也不同，要求在容量為c的背包中，裝盡可能價值高的物品，即使得背包中物品價值最高，且容量不超過c。

? 思路：要確定物品的狀態是裝還是不裝，第i個物品不裝的情況，則當前容量j小于第i個物品的重量w[i]，第i個物品不裝時的價值m[i][j]=m[i-1][j]，就為前i-1個物品的價值，若當前容量j>=w[i]，則可以裝入，相應的價值為前i-1個物品的價值再加上第i個物品的價值，則m[i][j]=m[i-1][j-w[i]]+v[i],?其中[j-w[i]]表示前i-1個物品的容量，拿當前背包總容量減去第i個物品容量

? 則 定義二維數組m[i][j]：表示i個物品在背包容量為j時所能包含的最大價值。

? 對于物品來說，不裝和裝的狀態轉移方程為：

? ? ? ? ? ? ? ? ?m[i-1][j]? ? ? ? ? ? ? ? ? ?j<w[i]

m[i][j]=? ? ?

? ? ? ? ? ? ? ? m[i-1][j-w[i]]+v[i]? ? ? ?j>=w[i]

初始條件在沒裝入物品的狀態下:m[i][j]=0

?

4.代碼如下：

public class package_01 {public static void main(String[]args){int c=12,n=6; //c為背包容量,n為物品數量int w[]={0,4,6,2,2,5,1}; //w[]表示各個物品的重量,初值為0int v[]={0,8,10,6,3,7,2}; //v[]表示各個物品的價值，初值為0int m[][]=new int[n+1][c+1]; //m[][]表示第i個物品在背包容量為j時所能包含的最大價值System.out.println("i\t"+"j\t"+"m[i][j]\t");for (int i = 1; i <=n ; i++) { //從第一件物品開始比較for (int j = 1; j <=c ; j++) { //從背包容量為1開始比較if (j>=w[i]){ //第i件物品容量滿足當前背包容量時，將之取進來(容量在不足于前件與當前件之和時，比較，取所能得到的最大價值的那一個)m[i][j]=Math.max(m[i-1][j],m[i-1][j-w[i]]+v[i]);System.out.println(i+"\t"+j+"\t"+m[i][j]);}elsem[i][j]=m[i-1][j]; //背包容量不滿足，則不取進來System.out.println(i+"\t"+j+"\t"+m[i][j]);}}System.out.println("The result is:"+m[n][c]); //二維數組中最后一個元素代表將最后一個比較完后所能取得的最大值} }

結果過程顯示：

i?? ?j?? ?m[i][j]?? ?
1?? ?1?? ?0
1?? ?2?? ?0
1?? ?3?? ?0
1?? ?4?? ?8
1?? ?4?? ?8
1?? ?5?? ?8
1?? ?5?? ?8
1?? ?6?? ?8
1?? ?6?? ?8
1?? ?7?? ?8
1?? ?7?? ?8
1?? ?8?? ?8
1?? ?8?? ?8
1?? ?9?? ?8
1?? ?9?? ?8
1?? ?10?? ?8
1?? ?10?? ?8
1?? ?11?? ?8
1?? ?11?? ?8
1?? ?12?? ?8
1?? ?12?? ?8
2?? ?1?? ?0
2?? ?2?? ?0
2?? ?3?? ?0
2?? ?4?? ?8
2?? ?5?? ?8
2?? ?6?? ?10
2?? ?6?? ?10
2?? ?7?? ?10
2?? ?7?? ?10
2?? ?8?? ?10
2?? ?8?? ?10
2?? ?9?? ?10
2?? ?9?? ?10
2?? ?10?? ?18
2?? ?10?? ?18
2?? ?11?? ?18
2?? ?11?? ?18
2?? ?12?? ?18
2?? ?12?? ?18
3?? ?1?? ?0
3?? ?2?? ?6
3?? ?2?? ?6
3?? ?3?? ?6
3?? ?3?? ?6
3?? ?4?? ?8
3?? ?4?? ?8
3?? ?5?? ?8
3?? ?5?? ?8
3?? ?6?? ?14
3?? ?6?? ?14
3?? ?7?? ?14
3?? ?7?? ?14
3?? ?8?? ?16
3?? ?8?? ?16
3?? ?9?? ?16
3?? ?9?? ?16
3?? ?10?? ?18
3?? ?10?? ?18
3?? ?11?? ?18
3?? ?11?? ?18
3?? ?12?? ?24
3?? ?12?? ?24
4?? ?1?? ?0
4?? ?2?? ?6
4?? ?2?? ?6
4?? ?3?? ?6
4?? ?3?? ?6
4?? ?4?? ?9
4?? ?4?? ?9
4?? ?5?? ?9
4?? ?5?? ?9
4?? ?6?? ?14
4?? ?6?? ?14
4?? ?7?? ?14
4?? ?7?? ?14
4?? ?8?? ?17
4?? ?8?? ?17
4?? ?9?? ?17
4?? ?9?? ?17
4?? ?10?? ?19
4?? ?10?? ?19
4?? ?11?? ?19
4?? ?11?? ?19
4?? ?12?? ?24
4?? ?12?? ?24
5?? ?1?? ?0
5?? ?2?? ?6
5?? ?3?? ?6
5?? ?4?? ?9
5?? ?5?? ?9
5?? ?5?? ?9
5?? ?6?? ?14
5?? ?6?? ?14
5?? ?7?? ?14
5?? ?7?? ?14
5?? ?8?? ?17
5?? ?8?? ?17
5?? ?9?? ?17
5?? ?9?? ?17
5?? ?10?? ?19
5?? ?10?? ?19
5?? ?11?? ?21
5?? ?11?? ?21
5?? ?12?? ?24
5?? ?12?? ?24
6?? ?1?? ?2
6?? ?1?? ?2
6?? ?2?? ?6
6?? ?2?? ?6
6?? ?3?? ?8
6?? ?3?? ?8
6?? ?4?? ?9
6?? ?4?? ?9
6?? ?5?? ?11
6?? ?5?? ?11
6?? ?6?? ?14
6?? ?6?? ?14
6?? ?7?? ?16
6?? ?7?? ?16
6?? ?8?? ?17
6?? ?8?? ?17
6?? ?9?? ?19
6?? ?9?? ?19
6?? ?10?? ?19
6?? ?10?? ?19
6?? ?11?? ?21
6?? ?11?? ?21
6?? ?12?? ?24
6?? ?12?? ?24
The result is:24
?

? ? ?

總結

以上是生活随笔為你收集整理的0/1背包问题——动态规划方法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。