1.介紹
動(dòng)態(tài)規(guī)劃(Dynamic Programming) 算法的核心思想, 將大問題劃分為小問題進(jìn)行解決,從而一步步獲取最優(yōu)解的處理算法
動(dòng)態(tài)算法 與 分治算法類似, 其基本思想也是將 待求解的大問題 分解為 若干個(gè)子問題, 先求解 子問題, 然后從這些 子問題的解得到源問題的解
與分治算法不同的是, 適合于 用動(dòng)態(tài)規(guī)劃求解的問題, 經(jīng)分解得到子問題往往不是相互獨(dú)立的.(即下一個(gè)子階段的求解 是 建立在上一個(gè) 子階段解 的 基礎(chǔ)上, 進(jìn)行進(jìn)一步的求解)
動(dòng)態(tài)規(guī)劃 可以通過填表的方式來逐步推進(jìn), 得到最優(yōu)解
2.實(shí)踐-背包問題
2.1 問題
背包問題: 有一個(gè)背包, 容量為 4磅, 現(xiàn)有如下物品
| 物品 | 重量 | 價(jià)格 |
|---|---|---|
| 吉他(G) | 1 | 1500 |
| 音響(S) | 4 | 3000 |
| 電腦(L) | 3 | 2000 |
要求:
1.達(dá)到目標(biāo)為 裝入的背包的總價(jià)值最大, 并且重量不超出
2.裝入物品不能重復(fù)
2.2 思路
1.背包問題主要是一個(gè)給定容量的背包,若干具有一定價(jià)值和重量的物品, 如何選擇物品放入背包使物品的價(jià)值最大. 其中又分 01背包和完全背包(完全背包指每種物品都有無限可用)
2.這里的問題屬于 01背包, 即每個(gè)物品最多放一個(gè), 而無限背包可以轉(zhuǎn)化 01背包.
3.算法的主要思想: 利用動(dòng)態(tài)規(guī)劃來解決. 每次遍歷的 第 i 個(gè)物品, 根據(jù) w[i] 和 v[i] 來確定是否需要將該物品放入背包中.即對于給定的n個(gè)物品. 設(shè)v[i], w[i]分別為第 i 個(gè)物品的價(jià)值 和 重量, C為背包的容量. 再令v[i] [j] 表示在前 i 個(gè)物品中能夠裝入容量為 j 的背包中的最大價(jià)值. 則我們有下面的結(jié)果:
(1)v[i] [0] = v[0] [j] = 0;//表示 填入表 第一行和第一列 是0
(2)當(dāng)w[i] > j 時(shí), v[i] [j] = v[i - 1] [j] //當(dāng)準(zhǔn)備加入新增的商品的容量大于 當(dāng)前背包的容量時(shí), 就直接使用上一個(gè)單元格的裝入策略;
(3) 當(dāng)j>=w[i]時(shí), v[i] [j] = max{v[i-1] [j], v[i] + v[i-1] [j - w[i]]}
//當(dāng) 準(zhǔn)備加入的新增的商品的容量小于等于當(dāng)前背包的容量
//裝入的方式
v[i-1] [j], 就是上一個(gè)單元格的裝入的最大值
v[i]:表示當(dāng)前商品的價(jià)值
v[i-1] [j-w[i]], 裝入i -1商品, 到剩余空間 j - w[i] 的最大值
當(dāng) j >= w[i]時(shí), v[i] [j] = max{v[i - 1] [j], v[i] +v[i - 1] [j - w[i]]}
2.3 代碼
public class KnapsackProblem {
public static void main(String[] args) {
//物品的重量
int[] w = {1, 4, 3};
//物品的價(jià)值, 這里val[i] 就是前面 v[i]
int[] val = {1500, 3000, 2000};
//背包的容量
int m = 4;
//物品的個(gè)數(shù)
int n = val.length;
//創(chuàng)建二維數(shù)組
//v[i][j] 表示在前 i 個(gè)物品中能夠裝入容量為 j 的背包中的最大價(jià)值
int[][] v = new int[n+1][m + 1];
//為了記錄放入商品的情況, 我們定一個(gè)二維數(shù)組
int[][] path = new int[n + 1][m + 1];
//初始化第一行和第一列, 這里在本程序中, 可以不去處理, 因?yàn)槟J(rèn)就是0
for (int i = 0; i < v.length; i++) {
//將第一列設(shè)置為0
v[i][0] = 0;
}
for (int i = 0; i < v[0].length; i++) {
//將第一行設(shè)置0
v[0][i] = 0;
}
//根據(jù)前面得到公式來動(dòng)態(tài)規(guī)劃處理
//不處理第一行 i是 從1開始的
for (int i = 1; i < v.length; i++) {
//不處理第一列, j是從1開始的
for (int j = 1; j < v[0].length; j++) {
//公式
//因?yàn)槲覀兂绦騣 是從1開始的, 因此原來公式中的 w[i-1]
if (w[i - 1] > j) {
v[i][j] = v[i-1][j];
} else {
//說明
//因?yàn)槲覀兊?i 從1開始的, 因此公式需要調(diào)整成
//v[i][j] = Math.max(v[i-1][j], val[i - 1] + v[i-1][j- w[i-1]])
//為了記錄商品存放到背包的情況, 我們不能直接的使用上面的公式, 需要使用if-else 來體現(xiàn)公式
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];
}
}
}
}
//輸出一下v看看目前的情況
for (int i = 0; i < v.length; i++) {
for (int j = 0; j < v[i].length; j++) {
System.out.println(v[i][j] + "");
}
System.out.println();
}
System.out.println("============================");
//輸出最后我們是放入的那些商品
//遍歷path, 這樣輸出會(huì)把所有的放入情況都得到, 其實(shí)我們只需要最后的放入
// for (int i = 0; i < path.length; i++) {
// for (int j = 0; j < path[i].length; j++) {
// if (path[i][j] == 1) {
// System.out.printf("第%d個(gè)商品放入到背包\n", i);
// }
// }
// }
//動(dòng)腦筋
//行的最大下標(biāo)
int i = path.length - 1;
//列的最大下標(biāo)
int j = path[0].length - 1;
while (i > 0 && j > 0) {
if (path[i][j] == 1) {
System.out.printf("第%d個(gè)商品放入到背包\n", i);
//w[i - 1]
j = w[i - 1];
}
i --;
}
}
}
