雁過無痕

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

多重背包問題：

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

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

若用F[i][j]表示對容量為j的背包，處理完前i種物品后，背包內(nèi)物品可達到的最大總價值，并記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)時間內(nèi)求出F[i][j]呢？

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

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

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

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

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

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

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

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

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

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

根據(jù)這個思路，可以對原來的公式進行如下調(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個數(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放入到一個隊列，那么，F[i][j]就是求這個隊列最大長度為m[i] + 1時，隊列中元素的最大值，加上a * w[i]。因而原問題可以轉(zhuǎn)化為：O(1)時間內(nèi)求一個隊列的最大值。

該問題可以這樣解決：

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

② 當指定隊列有元素M進入時，刪除隊列B中的比M小的（或隊列B中所指向的元素小等于M的）所有元素，并將元素M（或其地址）存入隊列B。

③ 當指定隊列有元素M離開時，隊列B中的第一個元素若與M相等（或隊列B第一個元素的地址與M相等），則隊列B的第一個元素也離隊。

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

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

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

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

由于w = v，上面的代碼可進行如下修改：

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

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

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

但這種做法相當?shù)托А嶋H上，這相當于一個“覆蓋”問題：在放入前i個物品后，體積為j的背包，只存在兩種狀態(tài)：是否能剛好裝滿，也就是，是否能被覆蓋。因而只要記錄下該狀態(tài)就可以了，前面的分析進行相應(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個數(shù)對應(yīng)的F[i - 1] [b + k * d]（其值為0或1）的最大值，即j前面的m[i] + 1個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++;  //隊列已滿，隊首元素出隊
25      *++pe = f[k];  //進隊
26      sum += f[k];     
27      if (! f[k] && sum != 0) f[k] = true; 
28      //f[k] = (bool)sum;       
29    }
30  }
31}
32

另外，可以倒著讀數(shù)據(jù)，這樣就不需要額外使用一個數(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個元素入隊，前面的判斷可以保證： 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;      //出隊: 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)中對隊列的元素個數(shù)進行判斷，這可以通過下面的方法避免，將循環(huán)拆分成兩部分：一部分都有入隊和出隊操作、另一部分只有入隊（或出隊）操作。

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

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

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

每計算一類物品，count數(shù)組都要初始化一次，比較費時，可以再用一個數(shù)組記錄上一次處理的物品編號，通過判斷上一次放入那一類的物品編號與當前這類物品編號是否一致（不一致時，相當于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為當前這類物品的編號
 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個元素入隊，前面的判斷可以保證： 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;      //出隊: 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

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

還有一種特例：

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

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