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