【轉】背包問題總結（0-1背包+完全背包+多重背包）

初始化的細節問題

我們看到的求最優解的背包問題題目中，事實上有兩種不太相同的問法。有的題目要求“恰好裝滿背包”時的最優解，有的題目則并沒有要求必須把背包裝滿。一種差別這兩種問法的實作方法是在初始化的時候有所不同。

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

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

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

這個小技巧完全可以推廣到其它類型的背包問題，後面也就不再對進行狀态轉移之前的初始化進行講解。

0-1 背包

有N件物品和一個容量為m的背包。第i件物品的費用是c[i]，價值是w[i]。求解将哪些物品裝入背包可使價值總和最大。

特點：每種物品僅有一件，可以選擇放或不放。

void ZeroOnePack(int cost, int weight)
{
   for (int i = m; i >= cost; i--)
      dp[i] = max(dp[i], dp[i-cost] + weight);
}
           

完全背包

有N種物品和一個容量為V的背包，每種物品都有無限件可用。第i種物品的費用是c[i]，價值是w[i]。求解将哪些物品裝入背包可使這些物品的費用總和不超過背包容量，且價值總和最大。

特點：每種物品都有無限件可用。

void CompletePack(int cost, int weight)
{
     for (int i = cost; i <= m; i++)
        dp[i] = max(dp[i], dp[i-cost] + weight);
}
           

多重背包

有N種物品和一個容量為V的背包。第i種物品最多有n[i]件可用，每件費用是c[i]，價值是w[i]。求解将哪些物品裝入背包可使這些物品的費用總和不超過背包容量，且價值總和最大。

特點：第i種物品最多有n[i]件可用。

注：

多重背包轉換成 01 背包問題中有個二進制分解思想。

把它的件數C 用分解成若幹個件數的集合，這裡面數字可以組合成任意小于等于C的件數，而且不會重複，之是以叫二進制分解，是因為這樣分解可以用數字的二進制形式來解釋

比如：7的二進制 7 = 111 它可以分解成 001 010 100 這三個數可以組合成任意小于等于7 的數，而且每種組合都會得到不同的數

           15 = 1111 可分解成 0001  0010  0100  1000 四個數字

如果13 = 1101 則分解為 0001 0010 0100 0110 前三個數字可以組合成7以内任意一個數，加上 0110 = 6 可以組合成任意一個大于6 小于13的數，雖然有重複但總是能把 13 以内所有的數都考慮到了。

基于這種 思想去把多件物品轉換為，多種一件物品，就可用01 背包求解了。

void MultiplePack(int cost, int weight, int amount)
{
    if (cost * amount >= m)
          CompletePack(cost, weight);
    else
    {
          int k = 1;
          while (k < amount)
          {    
               ZeroOnePack(k * cost, k * weight);
               amount -= k;
               k *= 2;
          }
          ZeroOnePack(amount * cost, amount * weight);
     }
}