資訊專欄INFORMATION COLUMN
摘要：背包問(wèn)題具體例子假設(shè)現(xiàn)有容量的背包，另外有個(gè)物品，分別為，，。最后，就是動(dòng)態(tài)規(guī)劃的思路了。而前個(gè)物體放入容量為的背包，又可以轉(zhuǎn)化成前個(gè)物體放入背包的問(wèn)題。
背包問(wèn)題具體例子：假設(shè)現(xiàn)有容量10kg的背包，另外有3個(gè)物品，分別為a1，a2，a3。物品a1重量為3kg，價(jià)值為4；物品a2重量為4kg，價(jià)值為5；物品a3重量為5kg，價(jià)值為6。將哪些物品放入背包可使得背包中的總價(jià)值最大？
首先想到的，一般是窮舉法，一個(gè)一個(gè)地試，對(duì)于數(shù)目小的例子適用，如果容量增大，物品增多，這種方法就無(wú)用武之地了。
其次，可以先把價(jià)值最大的物體放入，這已經(jīng)是貪婪算法的雛形了。如果不添加某些特定條件，結(jié)果未必可行。
最后，就是動(dòng)態(tài)規(guī)劃的思路了。先將原始問(wèn)題一般化，欲求背包能夠獲得的總價(jià)值，即欲求前i個(gè)物體放入容量為m（kg）背包的最大價(jià)值ci——使用一個(gè)數(shù)組來(lái)存儲(chǔ)最大價(jià)值，當(dāng)m取10，i取3時(shí)，即原始問(wèn)題了。而前i個(gè)物體放入容量為m（kg）的背包，又可以轉(zhuǎn)化成前(i-1)個(gè)物體放入背包的問(wèn)題。下面使用數(shù)學(xué)表達(dá)式描述它們兩者之間的具體關(guān)系。
表達(dá)式中各個(gè)符號(hào)的具體含義。
w[i] : 第i個(gè)物體的重量；
p[i] : 第i個(gè)物體的價(jià)值；
ci ： 前i個(gè)物體放入容量為m的背包的最大價(jià)值；
ci-1 ： 前i-1個(gè)物體放入容量為m的背包的最大價(jià)值；
ci-1] ： 前i-1個(gè)物體放入容量為m-w[i]的背包的最大價(jià)值；
由此可得：
ci=max{ci-1]+pi , ci-1}（下圖將給出更具體的解釋）
根據(jù)上式，對(duì)物體個(gè)數(shù)及背包重量進(jìn)行遞推，列出一個(gè)表格（見(jiàn)下表），表格來(lái)自（http://blog.csdn.net/fg2006/a...） ，當(dāng)逐步推出表中每個(gè)值的大小，那個(gè)最大價(jià)值就求出來(lái)了。推導(dǎo)過(guò)程中，注意一點(diǎn)，最好逐行而非逐列開(kāi)始推導(dǎo)，先從編號(hào)為1的那一行，推出所有c1的值，再推編號(hào)為2的那行c2的大小。這樣便于理解。
思路厘清后，開(kāi)始編程序，Java代碼如下所示:
public class BackPack {
public static void main(String[] args) {
int m = 10;
int n = 3;
int w[] = {3, 4, 5};
int p[] = {4, 5, 6};
int c[][] = BackPack_Solution(m, n, w, p);
for (int i = 1; i <=n; i++) {
for (int j = 1; j <=m; j++) {
System.out.print(c[i][j]+" ");
if(j==m){
System.out.println();
}
}
}
//printPack(c, w, m, n);
}
/**
* @param m 表示背包的最大容量
* @param n 表示商品個(gè)數(shù)
* @param w 表示商品重量數(shù)組
* @param p 表示商品價(jià)值數(shù)組
*/
public static int[][] BackPack_Solution(int m, int n, int[] w, int[] p) {
//c[i][v]表示前i件物品恰放入一個(gè)重量為m的背包可以獲得的最大價(jià)值
int c[][] = new int[n + 1][m + 1];
for (int i = 0; i < n + 1; i++)
c[i][0] = 0;
for (int j = 0; j < m + 1; j++)
c[0][j] = 0;
for (int i = 1; i < n + 1; i++) {
for (int j = 1; j < m + 1; j++) {
//當(dāng)物品為i件重量為j時(shí)，如果第i件的重量(w[i-1])小于重量j時(shí)，c[i][j]為下列兩種情況之一：
//(1)物品i不放入背包中，所以c[i][j]為c[i-1][j]的值
//(2)物品i放入背包中，則背包剩余重量為j-w[i-1],所以c[i][j]為c[i-1][j-w[i-1]]的值加上當(dāng)前物品i的價(jià)值
if (w[i - 1] <= j) {
if (c[i - 1][j] < (c[i - 1][j - w[i - 1]] + p[i - 1]))
c[i][j] = c[i - 1][j - w[i - 1]] + p[i - 1];
else
c[i][j] = c[i - 1][j];
} else
c[i][j] = c[i - 1][j];
}
}
return c;
}
運(yùn)行結(jié)果為：
0 0 4 4 4 4 4 4 4 4
0 0 4 5 5 5 9 9 9 9
0 0 4 5 6 6 9 10 11 11
Process finished with exit code 0
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/77005.html
摘要：首先說(shuō)下算法對(duì)于前端的作用和應(yīng)用作用不用說(shuō)了提高效率和性能應(yīng)用目前也是買了算法導(dǎo)論這本書，看得頭暈，各種數(shù)學(xué)知識(shí)需要返回去重新認(rèn)識(shí)，哎，終于知道了以前學(xué)的東西總有用的。。。 首先說(shuō)下算法對(duì)于前端的作用和應(yīng)用 作用：不用說(shuō)了提高效率和性能 應(yīng)用：目前也是買了算法導(dǎo)論這本書，看得頭暈，各種數(shù)學(xué)知識(shí)需要返回去重新認(rèn)識(shí)，哎，終于知道了以前學(xué)的東西總有用的。。。，自己買的哭著也要讀完，不扯了，直...
摘要：首先說(shuō)下算法對(duì)于前端的作用和應(yīng)用作用不用說(shuō)了提高效率和性能應(yīng)用目前也是買了算法導(dǎo)論這本書，看得頭暈，各種數(shù)學(xué)知識(shí)需要返回去重新認(rèn)識(shí)，哎，終于知道了以前學(xué)的東西總有用的。。。 首先說(shuō)下算法對(duì)于前端的作用和應(yīng)用 作用：不用說(shuō)了提高效率和性能 應(yīng)用：目前也是買了算法導(dǎo)論這本書，看得頭暈，各種數(shù)學(xué)知識(shí)需要返回去重新認(rèn)識(shí)，哎，終于知道了以前學(xué)的東西總有用的。。。，自己買的哭著也要讀完，不扯了，直...
摘要：首先說(shuō)下算法對(duì)于前端的作用和應(yīng)用作用不用說(shuō)了提高效率和性能應(yīng)用目前也是買了算法導(dǎo)論這本書，看得頭暈，各種數(shù)學(xué)知識(shí)需要返回去重新認(rèn)識(shí)，哎，終于知道了以前學(xué)的東西總有用的。。。 首先說(shuō)下算法對(duì)于前端的作用和應(yīng)用 作用：不用說(shuō)了提高效率和性能 應(yīng)用：目前也是買了算法導(dǎo)論這本書，看得頭暈，各種數(shù)學(xué)知識(shí)需要返回去重新認(rèn)識(shí)，哎，終于知道了以前學(xué)的東西總有用的。。。，自己買的哭著也要讀完，不扯了，直...
摘要：背包問(wèn)題題目給定種物品和一個(gè)容量為的背包，物品的體積是，其價(jià)值為。用子問(wèn)題定義狀態(tài)其狀態(tài)轉(zhuǎn)移方程是。 P01: 01背包問(wèn)題 題目 給定 N 種物品和一個(gè)容量為 V 的背包，物品 i 的體積是 wi，其價(jià)值為 ci 。(每種物品只有一個(gè))問(wèn)：如何選擇裝入背包的物品，使得裝入背包中的物品的總價(jià)值最大？ 面對(duì)每個(gè)物品，我們只有選擇放入或者不放入兩種選擇，每種物品只能放入一次。 我們用之前同...
閱讀 2699·2021-11-25 09:43
閱讀 2500·2021-09-22 15:29
閱讀 1022·2021-09-22 15:17
閱讀 3682·2021-09-03 10:36
閱讀 2257·2019-08-30 13:54
閱讀 1781·2019-08-30 11:23
閱讀 1192·2019-08-29 16:58
閱讀 1320·2019-08-29 16:14
