免费视频淫片aa毛片_日韩高清在线亚洲专区vr_日韩大片免费观看视频播放_亚洲欧美国产精品完整版

一. 動態(tài)規(guī)劃算法介紹：

動態(tài)規(guī)劃算法和分治算法類似，也是將待求解問題分成若干個小問題一步步求解，不同的是，每一個小問題求解過程依賴于上一個小問題的解。動態(tài)規(guī)劃問題可以通過填表法來得到解，最經(jīng)典的應(yīng)用就是背包問題。

二. 背包問題：

1. 背包問題介紹：

背包問題，就是有一個能裝重量為X的背包，現(xiàn)有重量W和價值V各不相同的幾件物品，在不超過背包容量X的情況下，如何使得背包內(nèi)物品的總價值V最大。如果可以裝相同的物品，稱為完全背包問題，不可以裝相同的物品，稱為01背包問題。

2. 填表法推導(dǎo)過程：

假如現(xiàn)有一個背包容量為4，現(xiàn)有3件物品，其價值和體積如下表：

在物品不能相同的情況下，如何裝才能使總價值最大呢？顯然是把A和C都裝進(jìn)背包，可以獲得總價值為35，這種情況是最優(yōu)的，那么是如何推導(dǎo)出來的呢？

我們可以把這個問題分成一個個的小問題來解決，現(xiàn)在的背包能裝的重量是4，那我們就看看背包容量為1、2、3、4的時候，裝東西能產(chǎn)生的最大價值分別是多少。這里要注意兩點：

• 分配容量的規(guī)則為最小重量的整數(shù)倍，這里物品最小重量是1，所以分別看背包容量為1、2、3、4時裝東西的最大價值；如果最小重量是2，那么就看背包容量為2、4的時候能裝的最大價值。

• 后一個問題的解依賴于前一個問題的解。

現(xiàn)在用填表法來解決這個背包問題：

首先說明一下這個表，0,1,2,3,4表示的是背包容量，A，B，C表示的是物品，“無”表示的是沒有物品的時候?？粘鰜淼母褡泳吞顚懏?dāng)前能夠得到的最大價值。顯然第二行和第二列都是0，第二行表示不裝東西的時候，那么不管背包容量是多少，不裝東西價值都是0；第一列表示背包容量為0的時候，啥都裝不了，所以價值也是0。

那么接下來就看第三行，即只裝物品A的時候，能夠得到的最大價值。因為規(guī)定了不能放入重復(fù)的物品，所以即使容量足夠的情況下也只能放入一件物品A，所以在容量不夠裝A之前，價值是0，能夠裝A之后，價值就是A的價值，即15。

接下來再看第四行，第四行的時候，不是只能裝B，之前說的那句話，“后一個問題的解依賴于前一個問題的解”，即第四行的時候，是要考慮裝A的情況，即要依賴第三行。

• 第四行第三列：容量為1，沒得選，因為B的重量是4，只能裝A，所以這里填15(沒得選的情況，就直接把上一行該列的值復(fù)制下來即可)；

• 第四行第四列：容量為2，也沒得選，復(fù)制上一行該列的值；

• 第四行第五列：容量為3，還是沒得選，復(fù)制上一行該列的值；

• 第四行第六列：容量為4，可以選擇裝B，也可以不裝B。怎么判斷裝不裝呢？看B的價值是否大于該列上一行的值，B的價值是30，而該列上一行的值是15,30更大，所以我們選擇裝B，這里填入30，而且裝了B之后就沒有剩余容量了。

來看最后一行：

• 第五行第三列：容量為1，沒得選，因為C的重量是3，裝不下，所以直接復(fù)制上一行該列的值，即15；

• 第五行第四列：容量為2，也沒得選，復(fù)制上一行該列的值；

• 第五行第五列：容量為3，可以選擇裝C，也可以選擇不裝復(fù)制上一行該列的值，但是C的價值是20，大于15，所以這里填20，而且裝了C之后沒有剩余容量了；

• 第五行第六列：容量為4，可以選擇裝C，也可以不裝C。不裝的話，就直接復(fù)制上一行該列的值，是30；如果裝C，C消耗的容量是3，價值是20，還剩余1個容量，那么就去容量為1的那一列，找一個最大值，是15，因為20 + 15 = 35 > 30，所以這里填入35。

通過上面這個推導(dǎo)過程可以發(fā)現(xiàn)，A對應(yīng)的這一行就只考慮物品A的情況，B這一行不僅要考慮B，還要考慮A，C這一行就要考慮A和B。當(dāng)有A、B、C三種物品且背包容量為4時，能夠獲得的最大價值就是C這一行，4對應(yīng)的這一列的值，即35。

3. 總結(jié)公式：

我們把上面的第二行第二列開始的部分看成是一個二維數(shù)組，如下：

所以二維數(shù)組可以定義成：

int[][] tv = new int[4][5]

tv[i][j]就表示前i個物品，裝入容量為j的背包時，能夠獲得的最大價值。4怎么來的？總共有3件物品，加上沒有物品的情況，就是4；5怎么來的？背包容量被我們拆成了1、2、3、4，再加上容量為0的情況，就是5。

我們再定義一個數(shù)組用來保存物品的重量：

int[] w = {1,4,3}; // 物品的重量

還需要定義一個數(shù)組來保存物品的價值：

int[] v = {15,30,20}; // 物品的價值

(1). tv[i][0] = 0，表示第一行都是0；tv[0][j] = 0，表示第一列都是0；

(2). w[i]表示的是第i件物品的重量，v[i]表示的是第i件物品的價值；j是列的索引，第0列表示背包容量為0時，第1列表示背包容量為1時，所以j表示的是當(dāng)前背包的容量。

(3). 當(dāng)w[i] > j時，那么就讓tv[i][j] = tv[i-1][j]。也就是說，第i件物品的重量大于當(dāng)前背包的容量時，那么久直接將上一行該列的那個值復(fù)制過來。

(4). 當(dāng)w[i] <= j時，那么就讓tv[i][j] = max{tv[i-1][j], v[i] + tv[i-1][j-w[i]]}。條件就是第i件物品的重量小于等于背包容量時，此時有兩種情況，一個是裝，一個是不裝，怎么判斷裝不裝呢，那就判斷裝能獲得的總價值更大還是不裝能獲得的總價值更大。

• 如果不裝第i件物品，能獲得的最大價值那就和上一行該列的值一樣，即tv[i-1][j]；

• 如果裝第i件物品，能夠獲得的最大價值就是第i件物品的價值加上裝了第i件物品后剩余容量能夠獲得的價值。v[i]是第i件物品的價值，怎么理解tv[i-1][j-w[i]]？首先看j-w[i]，意思就是當(dāng)前背包容量減去第i件物品的重量，那也就是當(dāng)前背包容量下如果裝第i件物品后剩余的容量，所以tv[i-1][j-w[i]]的意思就是，去上一行找背包容量為j-w[i]時的那個值，也就是當(dāng)前背包裝了第i件物品后剩余容量能夠獲得的最大價值；v[i] + tv[i-1][j-w[i]]就是如果裝第i件物品能夠獲得的最大價值。

• 經(jīng)過上面的分析，tv[i][j] = max{tv[i-1][j], v[i] + tv[i-1][j-w[i]]}就很好理解了，當(dāng)背包容量為j時，裝前i件物品能夠獲得的最大價值就是在裝與不裝兩種情況中取最大值。

3. 代碼實現(xiàn)：

public class BagProblem {
 
 public static void main(String[] args) {
  int[] w = {1,4,3}; // 物品的重量
  int[] v = {15,30,20}; // 物品的價值
  int m = 4; // 背包的容量
  System.out.println(maxValue(w, v, m));
 }
 
 public static int maxValue(int[] w, int[] v, int m) {
  int n = w.length; // 物品個數(shù)
  int[][] tv = new int[n+1][m+1];
  for(int i=0; i<v.length; i++) {
   tv[i][0] = 0; // 第一列全部設(shè)置為0
  }
  for(int i=0; i<tv[0].length; i++) {
   tv[0][i] = 0; // 第一行全部設(shè)置為0
  }
  for(int i=1; i<tv.length; i++) {
   for(int j=1; j<tv[0].length; j++) {
    if (w[i-1] > j) { // 循環(huán)中i從1開始，所以要減1
     tv[i][j] = tv[i-1][j];
    } else {
     // 循環(huán)中i從1開始，所以w和v中的i要減1
     tv[i][j] = Math.max(tv[i-1][j], v[i-1] + tv[i-1][j-w[i-1]]);
    }
   }
  }
  return tv[n][m];
 }

}