資訊專欄INFORMATION COLUMN
摘要：背包問題題目給定種物品和一個(gè)容量為的背包，物品的體積是，其價(jià)值為。用子問題定義狀態(tài)其狀態(tài)轉(zhuǎn)移方程是。
P01: 01背包問題
題目
給定 N 種物品和一個(gè)容量為 V 的背包，物品 i 的體積是 wi，其價(jià)值為 ci 。
(每種物品只有一個(gè))
問：如何選擇裝入背包的物品，使得裝入背包中的物品的總價(jià)值最大？
面對每個(gè)物品，我們只有選擇放入或者不放入兩種選擇，每種物品只能放入一次。
我們用之前同樣的思路來走一遍試試
假設(shè)只剩下最后一件物品，我們有兩種選擇
1.剩余空間足夠時(shí)，選擇放入
2.剩余空間不足時(shí)，不放入
所以我們有兩個(gè)最優(yōu)的子結(jié)構(gòu)：
1.容量為V的背包放入i-1件物品的最優(yōu)選擇
2.容量為V-w[i]的背包放入i-1件物品的最優(yōu)選擇
所以，綜合起來就是：
i 件物品放入容量為V的背包的最優(yōu)選擇：
max(容量為V的背包放入i-1件物品的最優(yōu)選擇，容量為V-w[i]的背包放入i-1件物品的最優(yōu)選擇+c[i])
我們用f[i] [v]表示前 i 件物品放入容量為 v 的背包中可以獲得的最大價(jià)值。
用子問題定義狀態(tài)：
其狀態(tài)轉(zhuǎn)移方程是：f[i] [v] = max{f[i-1] [v],f[i-1] [v-w[i]]+c[i]}。
我們先假設(shè)
背包總?cè)萘繛閂 = 12
物品的容量數(shù)組為 w = [4, 6, 2, 2, 5, 1]
價(jià)值數(shù)組為 c = [8, 10, 6, 3, 7, 2]
f(i,v) = 0 (i<=1, v
f(i,v) = c[0] (i==1, v>=p[0]);
f(i,v) = f(i-1,v) (i>1, v
f(i,v) = max(f(i-1,v), f(i-1,v-w[i-1])+c[i-1])(i>1, v>=w[i-1])
我們每次從左至右，保存前一次的數(shù)據(jù)
從上至下時(shí)，保存前一行的數(shù)據(jù)
所以我們總的來說只用保存一行的數(shù)據(jù)，空間復(fù)雜度為O(V)
時(shí)間復(fù)雜度為O(N*V),空間復(fù)雜度為O(V);
但是，如果我們用原始的遞歸辦法去做，即排列組合的方法去做時(shí)
時(shí)間復(fù)雜度為O(2^N);
那么當(dāng)V很大，N較小時(shí)，比如V=1000，N=6時(shí)，用遞歸只用計(jì)算2^6=64次，而備受推崇的動態(tài)規(guī)劃就需要計(jì)算1000*6=6000次
所以說，算法沒有絕對的好壞，關(guān)鍵要看應(yīng)用的慘景
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/96773.html
摘要：背包問題具體例子假設(shè)現(xiàn)有容量的背包，另外有個(gè)物品，分別為，，。最后，就是動態(tài)規(guī)劃的思路了。而前個(gè)物體放入容量為的背包，又可以轉(zhuǎn)化成前個(gè)物體放入背包的問題。 背包問題具體例子：假設(shè)現(xiàn)有容量10kg的背包，另外有3個(gè)物品，分別為a1，a2，a3。物品a1重量為3kg，價(jià)值為4；物品a2重量為4kg，價(jià)值為5；物品a3重量為5kg，價(jià)值為6。將哪些物品放入背包可使得背包中的總價(jià)值最大？ 首先...
摘要：動態(tài)規(guī)劃概念動態(tài)規(guī)劃過程每次決策依賴于當(dāng)前狀態(tài)，又隨即引起狀態(tài)的轉(zhuǎn)移。相關(guān)文章王者編程大賽之一王者編程大賽之二蓄水池王者編程大賽之四約瑟夫環(huán)王者編程大賽之五最短路徑 首發(fā)于 樊浩柏科學(xué)院 服務(wù)目前每月會對搬家?guī)煾颠M(jìn)行評級，根據(jù)師傅的評級排名結(jié)果，我們將優(yōu)先保證最優(yōu)師傅的全天訂單。 showImg(https://img3.fanhaobai.com/2017/12/2017-ziro...
摘要：狀態(tài)轉(zhuǎn)移方程背包問題的狀態(tài)轉(zhuǎn)移方程是其中即表示前件物品恰放入一個(gè)容量為的背包可以獲得的最大價(jià)值。求解將哪些物品裝入背包可使這些物品的體積總和不超過背包容量，且價(jià)值總和最大。 01背包 01背包的概念 有N件物品和一個(gè)容量為V的背包。第i件物品的費(fèi)用是c[i]，價(jià)值是w[i]。求解將哪些物品裝入背包可使價(jià)值總和最大。從這個(gè)題目中可以看出，01背包的特點(diǎn)就是：每種物品僅有一件，可以選擇放或...
摘要：首先說下算法對于前端的作用和應(yīng)用作用不用說了提高效率和性能應(yīng)用目前也是買了算法導(dǎo)論這本書，看得頭暈，各種數(shù)學(xué)知識需要返回去重新認(rèn)識，哎，終于知道了以前學(xué)的東西總有用的。。。 首先說下算法對于前端的作用和應(yīng)用 作用：不用說了提高效率和性能 應(yīng)用：目前也是買了算法導(dǎo)論這本書，看得頭暈，各種數(shù)學(xué)知識需要返回去重新認(rèn)識，哎，終于知道了以前學(xué)的東西總有用的。。。，自己買的哭著也要讀完，不扯了，直...
摘要：首先說下算法對于前端的作用和應(yīng)用作用不用說了提高效率和性能應(yīng)用目前也是買了算法導(dǎo)論這本書，看得頭暈，各種數(shù)學(xué)知識需要返回去重新認(rèn)識，哎，終于知道了以前學(xué)的東西總有用的。。。 首先說下算法對于前端的作用和應(yīng)用 作用：不用說了提高效率和性能 應(yīng)用：目前也是買了算法導(dǎo)論這本書，看得頭暈，各種數(shù)學(xué)知識需要返回去重新認(rèn)識，哎，終于知道了以前學(xué)的東西總有用的。。。，自己買的哭著也要讀完，不扯了，直...
閱讀 2855·2021-11-25 09:43
閱讀 1019·2021-10-11 10:57
閱讀 2513·2020-12-03 17:20
閱讀 3762·2019-08-30 14:05
閱讀 2447·2019-08-29 14:00
閱讀 2015·2019-08-29 12:37
閱讀 1696·2019-08-26 11:34
閱讀 3239·2019-08-26 10:27
