天天看點

【算法問題】0-1背包問題

  0-1背包問題:有一個賊在偷竊一家商店時,發現有n件物品,第i件物品價值vi元,重wi磅,此處vi與wi都是整數。他希望帶走的東西越值錢越好,但他的背包中至多隻能裝下W磅的東西,W為一整數。應該帶走哪幾樣東西?這個問題之是以稱為0-1背包,是因為每件物品或被帶走;或被留下;小偷不能隻帶走某個物品的一部分或帶走同一物品兩次。

  在分數(部分)背包問題(fractional knapsack problem)中,場景與上面問題一樣,但是竊賊可以帶走物品的一部分,而不必做出0-1的二分選擇。可以把0-1背包問題的一件物品想象成一個金錠,而部分問題中的一件物品則更像金沙。

  兩種背包問題都具有最優子結構性質。對0-1背包問題,考慮重量不超過W而價值最高的裝包方案。如果我們将商品j從此方案中删除,則剩餘商品必須是重量不超過W-wj的價值最高的方案(小偷隻能從不包括商品j的n-1個商品中選擇拿走哪些)。

  雖然兩個問題相似,但我們用貪心政策可以求解背包問題,而不能求解0-1背包問題,為了求解部分數背包問題,我們首先計算每個商品的每磅價值vi/wi。遵循貪心政策,小偷首先盡量多地拿走每磅價值最高的商品,如果該商品已全部拿走而背包未裝滿,他繼續盡量多地拿走每磅價值第二高的商品,依次類推,直到達到重量上限W。是以,通過将商品按每磅價值排序,貪心算法的時間運作時間是O(nlgn)。

  為了說明貪心這一貪心政策對0-1背包問題無效,考慮下圖所示的問題執行個體。此例包含3個商品和一個能容納50磅重量的背包。商品1重10磅,價值60美元。商品2重20磅,價值100美元。商品3重30磅,價值120美元。是以,商品1的每磅價值為6美元,高于商品2的每磅價值5美元和商品3的每磅價值4美元。是以,上述貪心政策會首先拿走商品1。但是,最優解應該是商品2和商品3,而留下商品1。拿走商品1的兩種方案都是次優的。

  但是,對于分數背包問題,上述貪心政策首先拿走商品1,是可以生成最優解的。拿走商品1的政策對0-1背包問題無效是因為小偷無法裝滿背包,空閑空間降低了方案的有效每磅價值。在0-1背包問題中,當我們考慮是否将一個商品裝入背包時,必須比較包含此商品的子問題的解與不包含它的子問題的解,然後才能做出選擇。這會導緻大量的重疊子問題——動态規劃的辨別。

【算法問題】0-1背包問題

例子:0-1背包問題。總共有三件物品,背包可容納5磅的東西,物品1重1磅,價值60元。物品2重2磅,價值100元,物品3重3磅,價值120元。怎麼才能最大化背包所裝物品的價值。

解答:我們可以得出物品一每磅價值60元,大于物品二的每磅50元和物品3的每磅40元。如果按照貪心算法的話就要取物品1。然而最優解應該取的是物品2和3,留下了1.

   在0-1背包問題中不應取物品1的原因在于這樣無法将背包填滿,空餘的空間就降低了貨物的有效每磅價值。

   我們可以利用動态規劃來解0-1背包問題。

   假設c[i]表示第i件物品的重量,w[i]表示第i件物品的價值,f[i][j]表示背包容量為j,可選物品為物品1~i時,背包能獲得的最大價值。

     用動态規劃求解即先求出背包容量較小時能獲得的最大價值,然後根據背包容量較小時的結果求出背包容量較大時的結果,也就是一個遞推的填表過程。

   當沒有可選物品時,背包能獲得的最大價值為0。即表格可初始化為

   

【算法問題】0-1背包問題
   填表過程(即狀态轉移方程)是:
【算法問題】0-1背包問題

  "j<c[i]"表示第i件物品的重量大于目前背包的容量j,此時顯然不放第i件物品。下面解釋上述方程在“其它“情況下的意義:”将前i件物品放入容量為j背包中“這個問題,如果隻考慮第i件物品放或者不放,那麼就可以轉化為隻涉及前i-1件物品的問題,即:

    1. 如果不放第i件物品,則問題轉化為隻涉及”前i-1件物品放入容量為j的背包中“

    2. 如果放第i件物品,則問題轉化為”前i-1件物品放入剩下的容量為j-c[i]的背包中“,此時能獲得的最大價值就是f[i-1][j-c[i]]再加上通過放入第i件物品獲得的價值獲得的價值w[i]。

    則在”其他“情況下,f[i][j]就是1、2中最大的那個值。

    顯然,可以從左下角利用狀态轉移方程依次逐行填表,得到f[3][5](表示可選物品為1、2、3,且背包容量為5時,能獲得的最大價值),可見動态規劃的确即為一個遞推的過程。填表後如下表所示:

    

【算法問題】0-1背包問題
    代碼如下:

int N = 3, V = 5;    //N是物品數量,V是背包容量
int c[4] = {0,1,2,3};
int w[4] = {0.60.100.120};
for (i = 0; i <= V; i++) { //逐行填表,i表示目前可選物品數,j表示目前背包的容量
    f[i][0] = 0;
    for (j = 1; j <= V; j++) {
        if (j < c[i]) {
            f[i][j] = f[i-1][j];
        } else {
            f[i][j] = max(f[i-1][j], f[i-1][j-c[i]] + w[i]);
        }
    }
}      

  

背包問題初始化

  求最優解的背包問題中,事實上有兩種不太相同的問法。有的題目要求”恰好裝滿背包“時的最優解,有的題目則沒有要求必須把背包裝滿。這兩種問法的差別是求解時的初始化不同。

  如果是第一種問法,要求恰好裝滿背包,那麼在初始化時除了f[0][0]為0,其他f[0][1~V]均設為-∞ ,這樣就可以包裝最終得到的解釋一種恰好裝滿背包的最優解。

  如果并沒有要求必須是把背包裝滿,而是隻希望價格盡量大,初始化時應該将f[0][1~V]全部設為0.

  這是為什麼呢?可以這樣了解:初始化的f數組事實上就是在沒有任何物品可以放入背包時的合法狀态。如果要求背包恰好裝滿,那麼此時隻有容量為0的背包可以在什麼也不裝且價值為0的情況下被”恰好裝滿“,其他容量的背包均沒有合法的解,屬于未定義的狀态,應該被指派為-∞。如果背包并非被必須裝滿,那麼任何容量的背包都有一個合法解”什麼都不裝“,這個解的價值為0,是以初始狀态的值也就全部為0了。