多重背包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ì)列”那部分算法，又沒說明得很清楚，看了幾遍沒看懂原理，只好自己動(dòng)腦去想怎么實(shí)現(xiàn)O(N*V)算法。
若用F[i][j]表示對(duì)容量為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è)思路，可以對(duì)原來的公式進(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) ㈡
對(duì)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ù)對(duì)應(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ì)列的最大值，對(duì)其采用的算法，越看越糊涂。其實(shí)，只要明白用一個(gè)“輔助隊(duì)列”，求另一個(gè)隊(duì)列的最值，那么具體的算法，和該“輔助隊(duì)列”的性質(zhì)（單調(diào)變化），都很容易推導(dǎo)出來。
在多重背包問題中，所有要進(jìn)入隊(duì)列的元素個(gè)數(shù)的上限值是已知的，可以直接用一個(gè)大數(shù)組模擬隊(duì)列。
1
const 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)整：
對(duì)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ù)對(duì)應(yīng)的F[i - 1] [b + k * d]（其值為0或1）的最大值，即j前面的m[i] + 1個(gè)0、1數(shù)據(jù)中是否存在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++; //隊(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ù)：
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ì)隊(duì)列的元素個(gè)數(shù)進(jìn)行判斷，這可以通過下面的方法避免，將循環(huán)拆分成兩部分：一部分都有入隊(duì)和出隊(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ù)組記錄上一次處理的物品編號(hào)，通過判斷上一次放入那一類的物品編號(hào)與當(dāng)前這類物品編號(hào)是否一致（不一致時(shí)，相當(dāng)于count[i]值為0的情況），從而避免對(duì)count數(shù)組的初始化操作。還可以將初始化count數(shù)組和后面的循環(huán)整合在一起。
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為當(dāng)前這類物品的編號(hào)
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 物品種類數(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ù)測(cè)試了下，上面提到的幾種方法，所用時(shí)間都是7秒多點(diǎn)，有排序的比沒排序的稍微快點(diǎn)。但在POJ上提交的結(jié)果，不同代碼的耗時(shí)相差挺大，快的在1秒左右，慢的接近1.5秒。
還有一種特例：
給定面值為1、2、5的紙幣若干個(gè)，問其所不能支付的最低價(jià)格（假設(shè)為自然數(shù)）。
這可以用多重背包（或母函數(shù)）來解決，但實(shí)際上是有O(1)解法的。