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