0/1 背包 完全背包 多重背包

背包問題算是一個蠻經典的演算法問題

這篇主要是以貪婪法來解決此問題，從最高單位價值開始取，取到滿為止

然後每一個物品皆是以可以分割的狀態來處理

 

舉例來說 有5個物品  背包總重w = 50

	Item1	Item2	Item3	Item4	Item5
w重量	10	20	30	10	20
v價值	60	100	120	30	40

 

首先會先計算每個物品的單位價值 v / w

計算後的結果如下

	Item1	Item2	Item3	Item4	Item5
單位價值	6	5	4	3	2

 

接著按照單位價值由小到大排序物品

	Item5	Item4	Item3	Item2	Item1
單位價值	2	3	4	5	6

 

然後從最高價值的開始取，取到剛好滿的重量

Item1 w=10 Item2 = 20  Item3 = 30

取到item3的時候發現背包裝不下，因此把item3切割成剛好的大小

最後的取得方式為 Item1: 1個  Item2: 1個  Item3: 0.667個

取得總價值為 60 * 1 + 100 * 1 + 120*0.667 =240.04

0/1 背包

有n 種不同的物品，每個物品有兩個屬性，size 體積，value 價值，現在給一個容量為 w 的背包，問最多可帶走多少價值的物品。  

完全背包 如果物品不計件數，就是每個物品不只一件的話，稍微改下即可 

01背包

V=10，N=3，c[]={3,4,5}, w={4,5,6}

（1）背包不一定裝滿

      計算順序是：從右往左，自上而下：因為每個物品只能放一次，前面的體積小的會影響體積大的

（2）背包剛好裝滿    

   計算順序是：從右往左，自上而下。注意初始值，其中-inf表示負無窮

完全背包：

V=10，N=3，c[]={3,4,5}, w={4,5,6}

（1）背包不一定裝滿

計算順序是：從左往右，自上而下：  每個物品可以放多次，前面的會影響後面的

（2）背包剛好裝滿

計算順序是：從左往右，自上而下。注意初始值，其中-inf表示負無窮

多重背包：  
多重背包問題要求很簡單，就是每件物品給出確定的件數，求可得到的最大價值  
   多重背包轉換成 01 背包問題就是多了個初始化，把它的件數C 用二進位分解成若干個件數的集合，這裡面數位可以組合成任意小於等於C的件數，而且不會重複，之所以叫二進位分解，是因為這樣分解可以用數位的二進位形式來解釋  
       比如：7的二進位 7 = 111 它可以分解成 001 010 100 這三個數可以組合成任意小於等於7 的數，而且每種組合都會得到不同的數  
       15 = 1111 可分解成 0001  0010  0100  1000 四個數字  
        如果13 = 1101 則分解為 0001 0010 0100 0110 前三個數位可以組合成  7以內任意一個數，即1、2、4可以組合為1——7內所有的數，加上 0110 = 6 可以組合成任意一個大於6 小於等於13的數，比如12，可以讓前面貢獻6且後面也貢獻6就行了。雖然有重複但總是能把 13 以內所有的數都考慮到了，基於這種思想去把多件物品轉換為，多種一件物品，就可用01 背包求解了。  

 copy

1.  int n;  //輸入有多少種物品  

2.  int c;  //每種物品有多少件  

3.  int v;  //每種物品的價值  

4.  int s;  //每種物品的尺寸  

5.  int count = 0; //分解後可得到多少種物品  

6.  int value[MAX]; //用來保存分解後的物品價值  

7.  int size[MAX];  //用來保存分解後物品體積  

8.    

9.  scanf("%d", &n);    //先輸入有多少種物品，接下來對每種物品進行分解  

10.  

11.while (n--)     //接下來輸入n中這個物品  

12.{  

13.    scanf("%d%d%d", &c, &s, &v);  //輸入每種物品的數目和價值  

14.    for (int k=1; k<=c; k<<=1)   //<<右移 相當於乘二  

15.    {  

16.        value[count] = k*v;  

17.        size[count++] = k*s;  

18.        c -= k;  

19.    }  

20.    if (c > 0)  

21.    {  

22.        value[count] = c*v;  

23.        size[count++] = c*s;  

24.    }  

25.}  

定理：一個正整數n可以被分解成1,2,4,…,2^(k-1),n-2^k+1（k是滿足n-2^k+1>0的最大整數）的形式，且1～n之內的所有整數均可以唯一表示成1,2,4,…,2^(k-1),n-2^k+1中某幾個數的和的形式。

證明如下：

（1） 數列1,2,4,…,2^(k-1),n-2^k+1中所有元素的和為n，所以若干元素的和的範圍為：[1, n]；

（2）如果正整數t<= 2^k – 1,則t一定能用1,2,4,…,2^(k-1)中某幾個數的和表示，這個很容易證明：我們把t的二進位表示寫出來，很明顯，t可以表示成n=a0*2^0+a1*2^1+…+ak*2^（k-1），其中ak=0或者1，表示t的第ak位二進位數字為0或者1.

（3）如果t>=2^k,設s=n-2^k+1，則t-s<=2^k-1，因而t-s可以表示成1,2,4,…,2^(k-1)中某幾個數的和的形式，進而t可以表示成1,2,4,…,2^(k-1)，s中某幾個數的和（加數中一定含有s）的形式。

（證畢！）

來源
http://www.csie.ntnu.edu.tw/~u91029/KnapsackProblem.html

Unbounded Knapsack Problem

無限背包問題

物品有許多種類，每一種物品都無限量供應的背包問題。

UVa 10465

演算法

分割問題的方式可以仿照 0/1 背包問題。 0/1 背包問題是一個物品的去留；無限背包問題則是一種物品的去留。考慮一種物品的各種用量：

c(n, w) = max(
   c(n-1, w - weight[n] ⋅ 0) + cost[n]     ,   用去零個第n種物品
   c(n-1, w - weight[n] ⋅ 1) + cost[n] ⋅ 1 ,   用去一個第n種物品
   c(n-1, w - weight[n] ⋅ 2) + cost[n] ⋅ 2 ,   用去兩個第n種物品
   ... ,                                       ...
)

n：第0種到第n種物品要放進背包內。
w：背包耐重限制。
c(n, w)：只有第0種到第n種物品，耐重限制為w，此時的背包問題答案。
weight[n]：第n種物品的重量。
cost[n]：第n種物品的價值。