0 1背包問題 01背包問題和普通背包區別 _生活百科

大家好,小編來為大家解答以上的問題。01背包問題和普通背包區別，0 1背包問題這個很多人還不知道,現在讓我們一起來看看吧！

文章插圖
1、"P01: 01背包問題題目有N件物品和1個容量為V的背包。
2、第i件物品的費用是c[i]，價值是w[i] 。
3、求解將哪些物品裝入背包可使價值總和最大。
4、基本思路這是最基礎的背包問題，特點是：每種物品僅有一件，可以選取放或不放。
5、用子問題定義狀態：即f[i][v]表示前i件物品恰放入1個容量為v的背包可以獲得的最大價值。
6、則其狀態轉移方程便是：f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}這個方程非常重要，基本上全部跟背包相關的問題的方程都是由它衍生出來的。
7、因此有必要將它清楚解釋一下：“將前i件物品放入容量為v的背包中”這個子問題，若只考慮第i件物品的策略（放或不放），那么就可以轉化為1個只牽扯前i-1件物品的問題。
8、假如不放第i件物品，那么問題就轉化為“前i-1件物品放入容量為v的背包中”，價值為f[i-1][v]；假如放第i件物品，那么問題就轉化為“前i-1件物品放入剩下的容量為v-c[i]的背包中”，此時能獲得的最大價值就是f[i-1][v-c[i]]再加上通過放入第i件物品獲得的價值w[i] 。
9、優化空間復雜度以上方法的時間和空間復雜度均為O(N*V)，其中時間復雜度基本已經不能再優化了，但空間復雜度卻可以優化到O(V) 。
10、先考慮上邊講的基本思路怎么實現，肯定是有1個主循環i=1..N，每回算出來二維數組f[i][0..V]的全部值。
11、那么，假如只用1個數組f[0..V]，能不能保證第i次循環結束后f[v]中表示的就是我們定義的狀態f[i][v]呢？f[i][v]是由f[i-1][v]和f[i-1][v-c[i]]2個子問題遞推而來，能否保證在推f[i][v]時（也即在第i次主循環中推f[v]時）能夠得到f[i-1][v]和f[i-1][v-c[i]]的值呢？事實上，這要求在每回主循環中我們以v=V..0的順序推f[v]，這樣才可以保證推f[v]時f[v-c[i]]保存的是狀態f[i-1][v-c[i]]的值。
12、偽代碼如下：for i=1..N for v=V..0 f[v]=max{f[v],f[v-c[i]]+w[i]};其中的f[v]=max{f[v],f[v-c[i]]}一句恰就相當于我們的轉移方程f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]}，由于目前的f[v-c[i]]就相當于原來的f[i-1][v-c[i]] 。
13、假如將v的循環順序從上邊的逆序改成順序的話，那么則成了f[i][v]由f[i][v-c[i]]推知，與本題意不符，但它卻是另1個重要的背包問題P02最簡捷的處理方案，故學習只用一維數組解01背包問題是十分必要的。
14、事實上，用一維數組解01背包的程序在后面會被多次用到，因此這里抽象出1個處理一件01背包中的物品過程，以后的代碼中直接調出使用不加說明。
15、過程ZeroOnePack，表示處理一件01背包中的物品，2個參數cost、weight分別表明這件物品的費用和價值。
16、procedure ZeroOnePack(cost,weight) for v=V..cost f[v]=max{f[v],f[v-cost]+weight}注意這個過程里的處理與前面給出的偽代碼有所不一樣。
17、前面的示例程序寫成v=V..0是為了在程序中體現每一個狀態都按照方程求解了，避免不必要的思維復雜度。
18、而這里既然已經抽象成看作黑箱的過程了，就可以加入優化。
19、費用為cost的物品不會影響狀態f[0..cost-1]，這是顯然的。
20、有了這個過程以后，01背包問題的偽代碼就可以這樣寫：for i=1..N ZeroOnePack(c[i],w[i]);初始化的細節問題我們看見的求最優解的背包問題題目中，事實上有兩種不太相同的問法。
21、有的題目要求“恰好裝滿背包”時的最優解，有的題目則并木有要求必須把背包裝滿。