雁過無痕

多重背包O(N*V)算法詳解（使用單調(diào)隊(duì)列）

多重背包問題：

有N種物品和容量為V的背包，若第i種物品，容量為v[i]，價(jià)值為w[i]，共有n[i]件。怎樣裝才能使背包內(nèi)的物品總價(jià)值最大？

網(wǎng)上關(guān)于“多重背包”的資料倒是不少，但是關(guān)于怎么實(shí)現(xiàn)O(N*V)算法的資料，真得好少呀，關(guān)于“單調(diào)隊(duì)列”那部分算法，又沒說明得很清楚，看了幾遍沒看懂原理，只好自己動腦去想怎么實(shí)現(xiàn)O(N*V)算法。

若用F[i][j]表示對容量為j的背包，處理完前i種物品后，背包內(nèi)物品可達(dá)到的最大總價(jià)值，并記m[i] = min(n[i], j / v[i])。放入背包的第i種物品的數(shù)目可以是：0、1、2……，可得：

F[i][j] = max { F[i - 1] [j – k * v[i] ] + k * w[i] }  (0 <= k <= m[i])       ㈠

如何在O(1)時(shí)間內(nèi)求出F[i][j]呢？

先看一個(gè)例子：取m[i] = 2, v[i] = v, w[i] = w, V > 9 * v，

并假設(shè) f(j) = F[i - 1][j]，觀察公式右邊要求最大值的幾項(xiàng)：

j = 6*v:   f(6*v)、f(5*v)+w、f(4*v)+2*w 這三個(gè)中的最大值

j = 5*v:   f(5*v)、f(4*v)+w、f(3*v)+2*w 這三個(gè)中的最大值

j = 4*v:   f(4*v)、f(3*v)+w、f(2*v)+2*w 這三個(gè)中的最大值

顯然，公式㈠右邊求最大值的幾項(xiàng)隨j值改變而改變，但如果將j = 6*v時(shí)，每項(xiàng)減去6*w，j=5*v時(shí)，每項(xiàng)減去5*w，j=4*v時(shí)，每項(xiàng)減去4*w，就得到：

j = 6*v:   f(6*v)-6*w、f(5*v)-5*w、f(4*v)-4*w 這三個(gè)中的最大值

j = 5*v:   f(5*v)-5*w、f(4*v)-4*w、f(3*v)-3*w 這三個(gè)中的最大值

j = 4*v:   f(4*v)-4*w、f(3*v)-3*w、f(2*v)-2*w 這三個(gè)中的最大值

很明顯，要求最大值的那些項(xiàng)，有很多重復(fù)。

根據(jù)這個(gè)思路，可以對原來的公式進(jìn)行如下調(diào)整：

假設(shè)d = v[i]，a = j / d，b = j % d，即 j = a * d + b，代入公式㈠，并用k替換a - k得：

F[i][j] = max { F[i - 1] [b + k * d] - k * w[i] } + a * w[i]   (a – m[i] <= k <= a)    ㈡

對F[i - 1][y] （y= b  b+d  b+2d  b+3d  b+4d  b+5d  b+6d  …  j）

F[i][j]就是求j的前面m[i] + 1個(gè)數(shù)對應(yīng)的F[i - 1] [b + k * d] - k * w[i]的最大值，加上a * w[i]，如果將F[i][j]前面所有的F[i - 1][b + k * d] – k * w放入到一個(gè)隊(duì)列，那么，F[i][j]就是求這個(gè)隊(duì)列最大長度為m[i] + 1時(shí)，隊(duì)列中元素的最大值，加上a * w[i]。因而原問題可以轉(zhuǎn)化為：O(1)時(shí)間內(nèi)求一個(gè)隊(duì)列的最大值。

該問題可以這樣解決：

① 用另一個(gè)隊(duì)列B記錄指定隊(duì)列的最大值（或者記錄最大值的地址），并通過下面兩個(gè)操作保證隊(duì)列B的第一個(gè)元素（或其所指向的元素）一定是指定隊(duì)列的當(dāng)前最大值。

② 當(dāng)指定隊(duì)列有元素M進(jìn)入時(shí)，刪除隊(duì)列B中的比M小的（或隊(duì)列B中所指向的元素小等于M的）所有元素，并將元素M（或其地址）存入隊(duì)列B。

③ 當(dāng)指定隊(duì)列有元素M離開時(shí)，隊(duì)列B中的第一個(gè)元素若與M相等（或隊(duì)列B第一個(gè)元素的地址與M相等），則隊(duì)列B的第一個(gè)元素也離隊(duì)。

經(jīng)過上述處理，可以保證隊(duì)列B中的第一個(gè)元素（或其指向的元素）一定是所指定隊(duì)列所有元素的最大值。顯然隊(duì)列B的元素（或其所指向的元素）是單調(diào)遞減的，這應(yīng)該就是《背包九講》中的提到的“單調(diào)隊(duì)列”吧，初看的時(shí)候被這個(gè)概念弄得稀里糊涂，網(wǎng)上的資料提到“維護(hù)隊(duì)列的最大值”，剛開始還以為是維護(hù)這個(gè)單調(diào)隊(duì)列的最大值，對其采用的算法，越看越糊涂。其實(shí)，只要明白用一個(gè)“輔助隊(duì)列”，求另一個(gè)隊(duì)列的最值，那么具體的算法，和該“輔助隊(duì)列”的性質(zhì)（單調(diào)變化），都很容易推導(dǎo)出來。

在多重背包問題中，所有要進(jìn)入隊(duì)列的元素個(gè)數(shù)的上限值是已知的，可以直接用一個(gè)大數(shù)組模擬隊(duì)列。

“多重背包”通用模板
 1const int MAX_V = 100004;
 2//v、n、w：當(dāng)前所處理的這類物品的體積、個(gè)數(shù)、價(jià)值
 3//V：背包體積， MAX_V：背包的體積上限值
 4//f[i]：體積為i的背包裝前幾種物品，能達(dá)到的價(jià)值上限。
 5inline void pack(int f[], int V, int v, int n, int w)
 6{
 7  if (n == 0 || v == 0) return;
 8  if (n == 1) {               //01背包
 9    for (int i = V; i >= v; --i)
10      if (f[i] < f[i - v] + w) f[i] = f[i - v] + w;
11    return;
12  }
13  if (n * v >= V - v + 1) {   //完全背包(n >= V / v)
14    for (int i = v; i <= V; ++i)
15      if (f[i] < f[i - v] + w) f[i] = f[i - v] + w;
16    return;    
17  }
18
19  int va[MAX_V], vb[MAX_V];   //va/vb: 主/輔助隊(duì)列
20  for (int j = 0; j < v; ++j) {     //多重背包
21    int *pb = va, *pe = va - 1;     //pb/pe分別指向隊(duì)列首/末元素
22    int *qb = vb, *qe = vb - 1;     //qb/qe分別指向輔助隊(duì)列首/末元素  
23    for (int k = j, i = 0; k <= V; k += v, ++i) {
24      if (pe  == pb + n) {       //若隊(duì)列大小達(dá)到指定值，第一個(gè)元素X出隊(duì)。
25        if (*pb == *qb) ++qb;   //若輔助隊(duì)列第一個(gè)元素等于X，該元素也出隊(duì)。 
26        ++pb;
27      }
28      int tt = f[k] - i * w;
29      *++pe = tt;                  //元素X進(jìn)隊(duì)
30      //刪除輔助隊(duì)列所有小于X的元素，qb到qe單調(diào)遞減，也可以用二分法
31      while (qe >= qb && *qe < tt) --qe;
32      *++qe = tt;              //元素X也存放入輔助隊(duì)列        
33      f[k] = *qb + i * w;      //輔助隊(duì)列首元素恒為指定隊(duì)列所有元素的最大值
34    }
35  }
36}
37
38

多重背包特例：物品價(jià)值和體積相等（w = v）

由于w = v，上面的代碼可進(jìn)行如下修改：

入隊(duì)的元素： tt = f[k] - (k / v) * w = f[k] - (k - j) = f[k] - k + j

    返回的最大值：*qb + (k / v) * w =  *qb + k - j

由于j是定值，可調(diào)整入隊(duì)的元素為: f[k] - k，最大值為 *qb + k

但這種做法相當(dāng)?shù)托А?shí)際上，這相當(dāng)于一個(gè)“覆蓋”問題：在放入前i個(gè)物品后，體積為j的背包，只存在兩種狀態(tài)：是否能剛好裝滿，也就是，是否能被覆蓋。因而只要記錄下該狀態(tài)就可以了，前面的分析進(jìn)行相應(yīng)的調(diào)整：

對F[i - 1][y] （y= b  b+d  b+2d  b+3d  b+4d  b+5d  b+6d  …  j）

F[i][j]就是求j的前面m[i] + 1個(gè)數(shù)對應(yīng)的F[i - 1] [b + k * d]（其值為0或1）的最大值，即j前面的m[i] + 1個(gè)0、1數(shù)據(jù)中是否存在1，這又可以簡化為判斷它們的和是否不等于0。

pack-01
 1const int MAX_V = 100004;
 2//w = v 特例
 3inline void pack(bool f[], int V, int v, int n)
 4{
 5  if (n == 0 || v == 0) return;
 6  if (n == 1) {  //01背包
 7    for (int i = V; i - v >= 0; --i)
 8      if (! f[i] && f[i - v]) f[i] = true;
 9      //if (f[i - v]) f[i] = true;
10    return;
11  }
12  if (n * v >= V - v + 1) {  //完全背包 n >= V / v
13    for (int i = v; i <= V; ++i)
14      if (! f[i] && f[i - v]) f[i] = true;
15      //if (f[i - v]) f[i] = true;      
16    return;
17  }
18  
19   bool va[MAX_V];
20    for (int j = 0; j < v; ++j) {     //多重背包
21    bool *pb = va, *pe = va - 1; 
22    size_t sum = 0;
23    for (int k = j; k <= V; k += v) {
24      if (pe == pb + n) sum -= *pb++;  //隊(duì)列已滿，隊(duì)首元素出隊(duì)
25      *++pe = f[k];  //進(jìn)隊(duì)
26      sum += f[k];     
27      if (! f[k] && sum != 0) f[k] = true; 
28      //f[k] = (bool)sum;       
29    }
30  }
31}
32

另外，可以倒著讀數(shù)據(jù)，這樣就不需要額外使用一個(gè)數(shù)組存放臨時(shí)數(shù)據(jù)：

pack-02
 1//w = v 特例
 2inline void pack(bool f[], int V, int v, int n)
 3{
 4  if (n == 0 || v == 0) return;
 5  if (n == 1) {  //01背包
 6    for (int i = V; i - v >= 0; --i)
 7      if (! f[i] && f[i - v]) f[i] = true;
 8      //if (f[i - v]) f[i] = true;
 9    return;
10  }
11  if (n * v >= V - v + 1) {  //完全背包 n >= V / v
12    for (int i = v; i <= V; ++i)
13      if (! f[i] && f[i - v]) f[i] = true;
14      //if (f[i - v]) f[i] = true;      
15    return;
16  }
17  
18  for (int j = 0; j < v; ++j) {    //多重背包
19    int k = V - j, sum = 0;
20    //前n + 1個(gè)元素入隊(duì)，前面的判斷可以保證： V - j - n * v > 0
21    for (; k >= std::max(0, V - j - n * v); k -= v) sum += f[k];
22    for (int i = V - j; i > 0; k -= v, i -= v) {
23      if (f[i]) --sum;      //出隊(duì): sum -= f[i] 
24      else if (sum != 0) f[i] = true;
25      //int tt = f[i]; f[i] = (bool)sum; sum -= tt;
26      if (k >= 0) sum += f[k];      
27    }
28  } 
29}
30

前面的代碼，都在循環(huán)中對隊(duì)列的元素個(gè)數(shù)進(jìn)行判斷，這可以通過下面的方法避免，將循環(huán)拆分成兩部分：一部分都有入隊(duì)和出隊(duì)操作、另一部分只有入隊(duì)（或出隊(duì)）操作。

對該特例，還有一種O(N * V)解法：用一個(gè)數(shù)組記錄當(dāng)前物品已經(jīng)使用數(shù)，關(guān)鍵代碼：

if (! f[i] && f[i - v] && count[i - v] < n)

f[i] = true, count[i] = count[i - v] + 1;

每計(jì)算一類物品，count數(shù)組都要初始化一次，比較費(fèi)時(shí)，可以再用一個(gè)數(shù)組記錄上一次處理的物品編號，通過判斷上一次放入那一類的物品編號與當(dāng)前這類物品編號是否一致（不一致時(shí)，相當(dāng)于count[i]值為0的情況），從而避免對count數(shù)組的初始化操作。還可以將初始化count數(shù)組和后面的循環(huán)整合在一起。

pack-1
1//pack-1  
2for (int i = 0; i <= V; ++i)  count[i] = 0;
3for (int i = v; i <= V; ++i) {     //多重背包
4  if (! f[i] && f[i - v] && count[i - v] < n) {
5    count[i] = count[i - v] + 1; 
6    f[i] = true;
7  }
8}
9

pack-2
 1//pack-2  cur為當(dāng)前這類物品的編號
 2for (int i = v; i <= V; ++i) {     //多重背包
 3  if (! f[i] && f[i - v]) {
 4    if (last[i - v] != cur)  count[i] = 1, last[i] = cur, f[i] = true;
 5    else if (count[i - v] < n) {
 6      count[i] = count[i - v] + 1; 
 7      last[i] = cur;
 8      f[i] = true;
 9    }
10  }
11}
12

pack-4
 1//pack-4
 2for (int i = v; i <= V; ++i) {     //多重背包
 3  if (f[i]) count[i] = 0;
 4  else if (f[i - v]) {
 5    if (i < 2 * v)  count[i] = 1, f[i] = true;  
 6    else if (count[i - v] < n) {
 7      count[i] = count[i - v] + 1;
 8      f[i] = true;
 9    }  
10  }
11}
12

POJ 1742：有若干不同面值的紙幣，問能組合出1到m中的幾種面值？

poj 1742
 1#include<algorithm>
 2#include<cstdio>
 3#define AB 1
 4
 5//MAX_N 物品種類數(shù)最大值 MAX_n每種物品數(shù)目的最大值，MAX_V背包體積最大值
 6const int MAX_N = 101, MAX_V = 100004;
 7
 8//w = v特例
 9inline void pack(bool f[], int V, int v, int n, int& total)
10{
11  //if (n == 0 || v == 0) return;
12  if (n == 1) {  //01背包
13    for (int i = V; i - v >= 0; --i)
14      if (! f[i] && f[i - v]) f[i] = true, ++total;
15    return;
16  }
17  if (n * v >= V - v + 1) {  //完全背包 n >= V / v
18    for (int i = v; i <= V; ++i)
19      if (! f[i] && f[i - v]) f[i] = true, ++total;
20    return;
21  }
22
23  for (int j = 0; j < v; ++j) {    //多重背包
24    int k = V - j, sum = 0;
25    //前n + 1個(gè)元素入隊(duì)，前面的判斷可以保證： V - j - n * v > 0
26    for (; k >= V - j - n * v; k -= v) sum += f[k];
27    for (int i = V - j; i > 0; k -= v, i -= v) {
28      if (f[i]) --sum;      //出隊(duì): sum -= f[i] 
29      else if (sum != 0) f[i] = true, ++total;
30      //int tt = f[i]; f[i] = (bool)sum; sum -= tt;
31      if (k >= 0) sum += f[k];      
32    }
33  }
34}
35
36struct Node {
37  int n, v, V;
38  bool operator<(const Node& other) const { return V < other.V;} 
39};
40
41int main()
42{
43#if AB == 1
44  freopen("src.txt","r",stdin);
45  freopen("z-b.txt","w",stdout);
46#endif  
47  Node node[MAX_N];
48  int V, N;
49  bool f[MAX_V];
50  while (scanf("%d %d",&N,&V) != EOF) {
51    if (N + V == 0) break;
52    Node *np = node + N;
53    for (Node *p = node; p < np; ++p) scanf("%d", &p->v);
54    for (Node *p = node; p < np; ++p) {
55      scanf("%d", &p->n);
56      p->V = std::min(p->n * p->v, V);
57    }
58    std::sort(node, np);
59    int total = 0;
60    f[0] = true;
61    for (int i = 1; i <= V; ++i) f[i] = false;
62    int mv = 0;
63    for (Node *p = node; p < np && total < V; ++p) {
64      mv = std::min(mv + p->V, V);
65      pack(f,mv,p->v,p->n, total);
66    }
67    printf("%d\n",total);
68  }
69}
70

用自己隨機(jī)生成的數(shù)據(jù)測試了下，上面提到的幾種方法，所用時(shí)間都是7秒多點(diǎn)，有排序的比沒排序的稍微快點(diǎn)。但在POJ上提交的結(jié)果，不同代碼的耗時(shí)相差挺大，快的在1秒左右，慢的接近1.5秒。

還有一種特例：

給定面值為1、2、5的紙幣若干個(gè)，問其所不能支付的最低價(jià)格（假設(shè)為自然數(shù)）。

這可以用多重背包（或母函數(shù)）來解決，但實(shí)際上是有O(1)解法的。