一. 動(dòng)態(tài)規(guī)劃算法介紹：
動(dòng)態(tài)規(guī)劃算法和分治算法類似，也是將待求解問題分成若干個(gè)小問題一步步求解，不同的是，每一個(gè)小問題求解過程依賴于上一個(gè)小問題的解。動(dòng)態(tài)規(guī)劃問題可以通過填表法來得到解，最經(jīng)典的應(yīng)用就是背包問題。
二. 背包問題：
1. 背包問題介紹：
背包問題，就是有一個(gè)能裝重量為X的背包，現(xiàn)有重量W和價(jià)值V各不相同的幾件物品，在不超過背包容量X的情況下，如何使得背包內(nèi)物品的總價(jià)值V最大。如果可以裝相同的物品，稱為完全背包問題，不可以裝相同的物品，稱為01背包問題。
2. 填表法推導(dǎo)過程：
假如現(xiàn)有一個(gè)背包容量為4，現(xiàn)有3件物品，其價(jià)值和體積如下表：
| 物品 | 重量W | 價(jià)值V |
|---|
| A | 1 | 15 |
| B | 4 | 30 |
| C | 3 | 20 |
在物品不能相同的情況下，如何裝才能使總價(jià)值最大呢？顯然是把A和C都裝進(jìn)背包，可以獲得總價(jià)值為35，這種情況是最優(yōu)的，那么是如何推導(dǎo)出來的呢？
我們可以把這個(gè)問題分成一個(gè)個(gè)的小問題來解決，現(xiàn)在的背包能裝的重量是4，那我們就看看背包容量為1、2、3、4的時(shí)候，裝東西能產(chǎn)生的最大價(jià)值分別是多少。這里要注意兩點(diǎn)：
分配容量的規(guī)則為最小重量的整數(shù)倍，這里物品最小重量是1，所以分別看背包容量為1、2、3、4時(shí)裝東西的最大價(jià)值；如果最小重量是2，那么就看背包容量為2、4的時(shí)候能裝的最大價(jià)值。
后一個(gè)問題的解依賴于前一個(gè)問題的解。
現(xiàn)在用填表法來解決這個(gè)背包問題：
首先說明一下這個(gè)表，0,1,2,3,4表示的是背包容量，A，B，C表示的是物品，“無”表示的是沒有物品的時(shí)候?？粘鰜淼母褡泳吞顚懏?dāng)前能夠得到的最大價(jià)值。顯然第二行和第二列都是0，第二行表示不裝東西的時(shí)候，那么不管背包容量是多少，不裝東西價(jià)值都是0；第一列表示背包容量為0的時(shí)候，啥都裝不了，所以價(jià)值也是0。
那么接下來就看第三行，即只裝物品A的時(shí)候，能夠得到的最大價(jià)值。因?yàn)橐?guī)定了不能放入重復(fù)的物品，所以即使容量足夠的情況下也只能放入一件物品A，所以在容量不夠裝A之前，價(jià)值是0，能夠裝A之后，價(jià)值就是A的價(jià)值，即15。
| 物品\背包容量 | 0 | 1 | 2 | 3 | 4 |
|---|
| 無 | 0 | 0 | 0 | 0 | 0 |
| A | 0 | 15 | 15 | 15 | 15 |
| B | 0 |
|
|
|
|
| C | 0 |
|
|
|
|
接下來再看第四行，第四行的時(shí)候，不是只能裝B，之前說的那句話，“后一個(gè)問題的解依賴于前一個(gè)問題的解”，即第四行的時(shí)候，是要考慮裝A的情況，即要依賴第三行。
第四行第三列：容量為1，沒得選，因?yàn)锽的重量是4，只能裝A，所以這里填15(沒得選的情況，就直接把上一行該列的值復(fù)制下來即可)；
第四行第四列：容量為2，也沒得選，復(fù)制上一行該列的值；
第四行第五列：容量為3，還是沒得選，復(fù)制上一行該列的值；
第四行第六列：容量為4，可以選擇裝B，也可以不裝B。怎么判斷裝不裝呢？看B的價(jià)值是否大于該列上一行的值，B的價(jià)值是30，而該列上一行的值是15,30更大，所以我們選擇裝B，這里填入30，而且裝了B之后就沒有剩余容量了。
| 物品\背包容量 | 0 | 1 | 2 | 3 | 4 |
|---|
| 無 | 0 | 0 | 0 | 0 | 0 |
| A | 0 | 15 | 15 | 15 | 15 |
| B | 0 | 15 | 15 | 15 | 30 |
| C | 0 |
|
|
|
|
來看最后一行：
第五行第三列：容量為1，沒得選，因?yàn)镃的重量是3，裝不下，所以直接復(fù)制上一行該列的值，即15；
第五行第四列：容量為2，也沒得選，復(fù)制上一行該列的值；
第五行第五列：容量為3，可以選擇裝C，也可以選擇不裝復(fù)制上一行該列的值，但是C的價(jià)值是20，大于15，所以這里填20，而且裝了C之后沒有剩余容量了；
第五行第六列：容量為4，可以選擇裝C，也可以不裝C。不裝的話，就直接復(fù)制上一行該列的值，是30；如果裝C，C消耗的容量是3，價(jià)值是20，還剩余1個(gè)容量，那么就去容量為1的那一列，找一個(gè)最大值，是15，因?yàn)?code style="font-size: 14px;padding: 2px 4px;border-radius: 4px;margin-right: 2px;margin-left: 2px;background-color: rgba(27, 31, 35, 0.05);font-family: "Operator Mono", Consolas, Monaco, Menlo, monospace;word-break: break-all;color: rgb(92, 157, 255);">20 + 15 = 35 > 30，所以這里填入35。
| 物品\背包容量 | 0 | 1 | 2 | 3 | 4 |
|---|
| 無 | 0 | 0 | 0 | 0 | 0 |
| A | 0 | 15 | 15 | 15 | 15 |
| B | 0 | 15 | 15 | 15 | 30 |
| C | 0 | 15 | 15 | 20 | 35 |
通過上面這個(gè)推導(dǎo)過程可以發(fā)現(xiàn)，A對(duì)應(yīng)的這一行就只考慮物品A的情況，B這一行不僅要考慮B，還要考慮A，C這一行就要考慮A和B。當(dāng)有A、B、C三種物品且背包容量為4時(shí)，能夠獲得的最大價(jià)值就是C這一行，4對(duì)應(yīng)的這一列的值，即35。
3. 總結(jié)公式：
我們把上面的第二行第二列開始的部分看成是一個(gè)二維數(shù)組，如下：
| 0 | 0 | 0 | 0 | 0 |
|---|
| 0 | 15 | 15 | 15 | 15 |
| 0 | 15 | 15 | 15 | 30 |
| 0 | 15 | 15 | 20 | 35 |
所以二維數(shù)組可以定義成：
int[][] tv = new int[4][5]
tv[i][j]就表示前i個(gè)物品，裝入容量為j的背包時(shí)，能夠獲得的最大價(jià)值。4怎么來的？總共有3件物品，加上沒有物品的情況，就是4；5怎么來的？背包容量被我們拆成了1、2、3、4，再加上容量為0的情況，就是5。
我們?cè)俣x一個(gè)數(shù)組用來保存物品的重量：
int[] w = {1,4,3}; // 物品的重量
還需要定義一個(gè)數(shù)組來保存物品的價(jià)值：
int[] v = {15,30,20}; // 物品的價(jià)值
(1). tv[i][0] = 0，表示第一行都是0；tv[0][j] = 0，表示第一列都是0；
(2). w[i]表示的是第i件物品的重量，v[i]表示的是第i件物品的價(jià)值；j是列的索引，第0列表示背包容量為0時(shí)，第1列表示背包容量為1時(shí)，所以j表示的是當(dāng)前背包的容量。
(3). 當(dāng)w[i] > j時(shí)，那么就讓tv[i][j] = tv[i-1][j]。也就是說，第i件物品的重量大于當(dāng)前背包的容量時(shí)，那么久直接將上一行該列的那個(gè)值復(fù)制過來。
(4). 當(dāng)w[i] <= j時(shí)，那么就讓tv[i][j] = max{tv[i-1][j], v[i] + tv[i-1][j-w[i]]}。條件就是第i件物品的重量小于等于背包容量時(shí)，此時(shí)有兩種情況，一個(gè)是裝，一個(gè)是不裝，怎么判斷裝不裝呢，那就判斷裝能獲得的總價(jià)值更大還是不裝能獲得的總價(jià)值更大。
如果不裝第i件物品，能獲得的最大價(jià)值那就和上一行該列的值一樣，即tv[i-1][j]；
如果裝第i件物品，能夠獲得的最大價(jià)值就是第i件物品的價(jià)值加上裝了第i件物品后剩余容量能夠獲得的價(jià)值。v[i]是第i件物品的價(jià)值，怎么理解tv[i-1][j-w[i]]？首先看j-w[i]，意思就是當(dāng)前背包容量減去第i件物品的重量，那也就是當(dāng)前背包容量下如果裝第i件物品后剩余的容量，所以tv[i-1][j-w[i]]的意思就是，去上一行找背包容量為j-w[i]時(shí)的那個(gè)值，也就是當(dāng)前背包裝了第i件物品后剩余容量能夠獲得的最大價(jià)值；v[i] + tv[i-1][j-w[i]]就是如果裝第i件物品能夠獲得的最大價(jià)值。
經(jīng)過上面的分析，tv[i][j] = max{tv[i-1][j], v[i] + tv[i-1][j-w[i]]}就很好理解了，當(dāng)背包容量為j時(shí)，裝前i件物品能夠獲得的最大價(jià)值就是在裝與不裝兩種情況中取最大值。
3. 代碼實(shí)現(xiàn)：
public class BagProblem {
public static void main(String[] args) {
int[] w = {1,4,3}; // 物品的重量
int[] v = {15,30,20}; // 物品的價(jià)值
int m = 4; // 背包的容量
System.out.println(maxValue(w, v, m));
}
public static int maxValue(int[] w, int[] v, int m) {
int n = w.length; // 物品個(gè)數(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];
}
}
