多重背包O(N*V)算法詳解（使用單調隊列）
多重背包問題：
有N種物品和容量為V的背包，若第i種物品，容量為v[i]，價值為w[i]，共有n[i]件。怎樣裝才能使背包內的物品總價值最大？
網上關于“多重背包”的資料倒是不少，但是關于怎么實現O(N*V)算法的資料，真得好少呀，關于“單調隊列”那部分算法，又沒說明得很清楚，看了幾遍沒看懂原理，只好自己動腦去想怎么實現O(N*V)算法。
若用F[i][j]表示對容量為j的背包，處理完前i種物品后，背包內物品可達到的最大總價值，并記m[i] = min(n[i], j / v[i])。放入背包的第i種物品的數目可以是：0、1、2……，可得：
F[i][j] = max { F[i - 1] [j – k * v[i] ] + k * w[i] } (0 <= k <= m[i]) ㈠
如何在O(1)時間內求出F[i][j]呢？
先看一個例子：取m[i] = 2, v[i] = v, w[i] = w, V > 9 * v，
并假設 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 這三個中的最大值
很明顯，要求最大值的那些項，有很多重復。
根據這個思路，可以對原來的公式進行如下調整：
假設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個數對應的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]。因而原問題可以轉化為：O(1)時間內求一個隊列的最大值。
該問題可以這樣解決：
① 用另一個隊列B記錄指定隊列的最大值（或者記錄最大值的地址），并通過下面兩個操作保證隊列B的第一個元素（或其所指向的元素）一定是指定隊列的當前最大值。
② 當指定隊列有元素M進入時，刪除隊列B中的比M小的（或隊列B中所指向的元素小等于M的）所有元素，并將元素M（或其地址）存入隊列B。
③ 當指定隊列有元素M離開時，隊列B中的第一個元素若與M相等（或隊列B第一個元素的地址與M相等），則隊列B的第一個元素也離隊。
經過上述處理，可以保證隊列B中的第一個元素（或其指向的元素）一定是所指定隊列所有元素的最大值。顯然隊列B的元素（或其所指向的元素）是單調遞減的，這應該就是《背包九講》中的提到的“單調隊列”吧，初看的時候被這個概念弄得稀里糊涂，網上的資料提到“維護隊列的最大值”，剛開始還以為是維護這個單調隊列的最大值，對其采用的算法，越看越糊涂。其實，只要明白用一個“輔助隊列”，求另一個隊列的最值，那么具體的算法，和該“輔助隊列”的性質（單調變化），都很容易推導出來。
在多重背包問題中，所有要進入隊列的元素個數的上限值是已知的，可以直接用一個大數組模擬隊列。
1
const int MAX_V = 100004;
2//v、n、w：當前所處理的這類物品的體積、個數、價值
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單調遞減，也可以用二分法
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是定值，可調整入隊的元素為: f[k] - k，最大值為 *qb + k
但這種做法相當低效。實際上，這相當于一個“覆蓋”問題：在放入前i個物品后，體積為j的背包，只存在兩種狀態：是否能剛好裝滿，也就是，是否能被覆蓋。因而只要記錄下該狀態就可以了，前面的分析進行相應的調整：
對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個數對應的F[i - 1] [b + k * d]（其值為0或1）的最大值，即j前面的m[i] + 1個0、1數據中是否存在1，這又可以簡化為判斷它們的和是否不等于0。
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
另外，可以倒著讀數據，這樣就不需要額外使用一個數組存放臨時數據：
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
前面的代碼，都在循環中對隊列的元素個數進行判斷，這可以通過下面的方法避免，將循環拆分成兩部分：一部分都有入隊和出隊操作、另一部分只有入隊（或出隊）操作。
對該特例，還有一種O(N * V)解法：用一個數組記錄當前物品已經使用數，關鍵代碼：
if (! f[i] && f[i - v] && count[i - v] < n)
f[i] = true, count[i] = count[i - v] + 1;
每計算一類物品，count數組都要初始化一次，比較費時，可以再用一個數組記錄上一次處理的物品編號，通過判斷上一次放入那一類的物品編號與當前這類物品編號是否一致（不一致時，相當于count[i]值為0的情況），從而避免對count數組的初始化操作。還可以將初始化count數組和后面的循環整合在一起。
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
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
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中的幾種面值？
1#include<algorithm>
2#include<cstdio>
3#define AB 1
4
5//MAX_N 物品種類數最大值 MAX_n每種物品數目的最大值，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
用自己隨機生成的數據測試了下，上面提到的幾種方法，所用時間都是7秒多點，有排序的比沒排序的稍微快點。但在POJ上提交的結果，不同代碼的耗時相差挺大，快的在1秒左右，慢的接近1.5秒。
還有一種特例：
給定面值為1、2、5的紙幣若干個，問其所不能支付的最低價格（假設為自然數）。
這可以用多重背包（或母函數）來解決，但實際上是有O(1)解法的。