淺談背包問題 (0/1 Knapsack Problem) 優化那些事

contents

  1. 1. 輸入格式
  2. 2. 輸出格式
  3. 3. 範例輸入 1
  4. 4. 範例輸出 1
  5. 5. 範例輸入 2
  6. 6. 範例輸出 2
  7. 7. Solution
    1. 7.1. Branch-and-bound
      1. 7.1.1. 結論
    2. 7.2. Dynamic Programming
      1. 7.2.1. 前言
      2. 7.2.2. 優化初夜
      3. 7.2.3. 優化二夜

收錄於 批改娘 20005. 0/1 Knapsack Problem。之所以有機會談到這個問題,其原因於早期的背包問題,大多都是用 branch-and-bound 算法來完成,也因此學弟課程出了這一份作業,大部分的測資,使用 branch-and-bound 能跑得比一般記憶體化 DP 快上非常多。當然,作為一個 Morris(?) 怎能允許這樣的事情發生。

現在回顧一下背包問題的模型吧!

輸入格式

每組測資第一行包含兩個正整數,分別代表背包大小 $M$ ($\leq 5×10^6$) 和物品個數 $N$ ($\leq 1000$),下一行開始每行包含兩個正整數,分別代表物品價值 $P_i$ ($\leq 10^5$)和物品重量 $W_i$ ($ \leq 10^5$)。

輸出格式

對於每組測資,請輸出最大收益。

範例輸入 1

1
2
3
4
5
6
7
8
50 7
70 31
20 10
39 20
37 19
7 4
5 3
10 6

範例輸出 1

1
107

範例輸入 2

1
2
3
4
5
6
7
8
170 7
442 41
525 50
511 49
593 59
546 55
564 57
617 60

範例輸出 2

1
1735

Solution

Branch-and-bound

bound knapscak problem 古耕竹同學提供

如果物品可以被切割,那麼可以利用物品的 CP 值 ($\textit{cp}_i = p_i/w_i$)排序,使用貪心算法在 $O(N \log N)$ 找到最佳解。然而,背包問題在於物品只能挑或不挑,一旦無法切割物品,那麼貪心算法無法將剩餘的部分填滿,進而可能產生更好的一組解填滿剩餘部分。

想要更快嗎?多看論文且實作它吧!

branch-and-bound 基本核心操作為

  • 按照 CP 值由大到小排序
  • 貪心法最佳解 $\textit{bound}$
  • 進行深度優先搜索,優先挑 CP 值大的入選
    • 當前挑選方案最佳解 $g$ + 剩餘物品使用貪心法最佳解 $g$ 小於等於當前最佳解 $\textit{bound}$,則退出搜索。
    • 更新 $\textit{bound} = \max(\textit{bound}, g)$
    • 選擇加入 或 不加入 (註:學弟說我的某些測資,通通優先不選可以快個數十倍)

參考代碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <bits/stdc++.h>
using namespace std;
struct Item {
int v, w;
double cp() {
return (double) v / w;
}
};
int cmpCP(Item a, Item b) {
double cpA = a.cp();
double cpB = b.cp();
if (cpA == cpB)
return a.w > b.w;
return cpA > cpB;
}
int n, m;
int ret = 0;
Item items[1005];
int prefixW[1005];
int prefixV[1005];
int h(int i, int w, int b, int &j, int &f) {
int fw = i == 0 ? w : (w + prefixW[i-1]);
for (j = max(b, i); j < n && prefixW[j] <= fw; j++);
if (j >= n) {
return prefixV[n-1];
}
int v = 0;
f = 0;
v += prefixV[j-1] - (i == 0 ? 0 : prefixV[i-1]);
w -= prefixW[j-1] - (i == 0 ? 0 : prefixW[i-1]);
if (w != 0) {
f = 1;
float k = (float) w / items[j].w;
w -= k * items[j].w;
v += k * items[j].v;
}
return v;
}
int greedy(int w) {
int v = 0;
for(int i = 0; i < n; i++) {
if (w >= items[i].w){
w -= items[i].w;
v += items[i].v;
} else {
return v;
}
}
return v;
}
void dfs(int i, int w, int v, int b) {
if (i >= n) {
ret = max(ret, v);
return;
}
int j = n, f;
int hv = v + h(i, w, b, j, f);
if (hv <= ret)
return;
if (f == 0) {
ret = max(ret, hv);
return;
}
if (w >= items[i].w)
dfs(i + 1, w - items[i].w, v + items[i].v, j);
dfs(i + 1, w, v, j);
return;
}
int main() {
while (scanf("%d %d", &m, &n) == 2) {
for (int i = 0; i < n; i++)
scanf("%d %d", &items[i].v, &items[i].w);
stable_sort(items, items+n, cmpCP);
for (int i = 0, w = 0, v = 0; i < n; i++) {
w += items[i].w;
v += items[i].v;
prefixW[i] = w;
prefixV[i] = v;
}
ret = greedy(m);
dfs(0, m, 0, 0);
printf("%d\n", ret);
}
return 0;
}

結論

branch-and-bound 空間複雜度只跟 $N$ 有關,使用記憶體空間小,相較於記憶化搜索有較少的 cache miss,速度取決於搜索順序。對於同一 CP 的等價處理薄弱,一遇到這種情況,搜尋時間瞬間指數次方上去,可以等個昏天暗地。

Dynamic Programming

前言

請不要忘記背包問題屬於 NP-Complete,我們能做的事情只能優化計算,最慘的情況仍要面對,優化常數是可以努力的方向,讓我們嘗試變得更快吧。

基礎寫法解說請參考 DJWS - Bounded Knapsack Problem 的說明。

從定義上,我們通常會宣告 dp[i][j] 表示放入前 $i$ 個物品時,總共最多為 $j$ 的最大價值為何。這樣空間宣告使用 $\mathcal{O}(NW)$。在實作上,我們可以藉由運算順序將空間降為 $\mathcal{O}(W)$。因此,寫出以下代碼並不難

1
2
3
4
5
int dp[MAXW];
memset(dp, 0, sizeof(dp));
for (int i = 0; i < N; i++)
for (int j = W; j >= w[i]; j--)
dp[j] = max(dp[j], dp[j-w[i]]+v[i]);

優化初夜

從實際運行上,我們可以發現每次跑 $\mathcal{\theta}(W)$ 非常浪費,只需要跑 $\min(W, \sum w_i)$ 即可。因此,第一份計算量優化如下

1
2
3
4
5
6
7
int dp[MAXW];
memset(dp, 0, sizeof(dp));
for (int i = 0, sum = 0; i < N; i++) {
sum += w[i];
for (int j = min(W, sum); j >= w[i]; j--)
dp[j] = max(dp[j], dp[j-w[i]]+v[i]);
}

計算邊界優化通常可以達到 2x 加速

如此一來,在數量多權重小時,剛啟動的效能時可以賺到非常多。然而,不乏第一次就給權重的大的,目標最小化 $\sum \text{sum}_i$,從數學觀念很明顯地瞭解,只要一開始將權重 $w_i$ 由小到大排序即可,這樣能保證最小化計算量!

1
2
3
4
5
6
7
8
int dp[MAXW];
memset(dp, 0, sizeof(dp));
sort (w, v) by w
for (int i = 0, sum = 0; i < N; i++) {
sum += w[i];
for (int j = min(W, sum); j >= w[i]; j--)
dp[j] = max(dp[j], dp[j-w[i]]+v[i]);
}

數學使得我們更進一步,達到 1.5x 加速

優化二夜

經由平行的訓練,也許我們可以更往上一層優化。

接下來,打算把物品拆成兩堆,再利用優化初夜學到的技巧,就能引爆更多計算邊界優化。如果拆成三堆以上,合併操作變得相當複雜,當只有兩堆時,保證合併效能一定在 $\mathcal{\theta}(W)$ 完成。

如何合併兩堆的計算結果,假設 dp1[i] 表示其中一堆重量小於等於 $i$ 的最佳解,同理 dp2[j] 的計算結果。

當要湊出重量為 $W$ 的最佳解時,窮舉其中一堆的重量 $i$ 維護其中一堆的前綴最大值 $j$,相當於使用掃描線算法在線性時間內合併。合併操作如下:

1
2
3
4
5
int ret = 0;
for (int i = 0, j = W, mx = 0; i <= W; i++, j--) {
mx = max(mx, dp2[i]);
ret = max(ret, dp1[j] + mx);
}

Divide-and-Conquer,使得我們更快再更快!達到 1.5 加速

然而,優化問題將轉移到最佳分堆策略,好的分堆策略將使得計算量下降更多。目標分兩堆,使得 $\sum \text{sum1}_i + \sum \text{sum2}_i$ 最小化。明顯地,由小到大排序物品重量,依序將物品放到總和最小的那一堆即可。最後,我們整合每一夜的結果如下:

一個好的分堆,達到 1.2x 加速

相信在不久之後,還有更好的優化策略,也許不是延伸,而是全新的面貌。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <bits/stdc++.h>
using namespace std;
namespace {
static const int MAXW = 5000005;
static const int MAXN = 1005;
static void run(int A[][2], int dp[], int W, int N) {
for (int i = 0, sum = 0; i < N; i++) {
int w = A[i][0], v = A[i][1];
for (int j = min(W, sum + w); j >= w; j--)
dp[j] = max(dp[j], dp[j-w]+v);
sum += w;
}
}
static int knapsack(int C[][2], int N, int W) {
vector< pair<int, int> > A;
for (int i = 0; i < N; i++)
A.push_back(make_pair(C[i][0], C[i][1]));
N = A.size();
assert(N < MAXN);
static int dp1[MAXW+1], dp2[MAXW+1];
int Ar[2][MAXN][2], ArN[2] = {};
memset(dp1, 0, sizeof(dp1[0])*(W+1));
memset(dp2, 0, sizeof(dp2[0])*(W+1));
sort(A.begin(), A.end());
int sum[2] = {};
for (int i = 0; i < N; i++) {
int ch = sum[1] < sum[0];
Ar[ch][ArN[ch]][0] = A[i].first;
Ar[ch][ArN[ch]][1] = A[i].second;
ArN[ch]++;
sum[ch] += A[i].first;
}
run(Ar[0], dp1, W, ArN[0]);
run(Ar[1], dp2, W, ArN[1]);
int ret = 0;
for (int i = 0, j = W, mx = 0; i <= W; i++, j--) {
mx = max(mx, dp2[i]);
ret = max(ret, dp1[j] + mx);
}
return ret;
}
}
int main() {
int W, N, C[MAXN][2];
while (scanf("%d %d", &W, &N) == 2) {
for (int i = 0; i < N; i++)
assert(scanf("%d %d", &C[i][1], &C[i][0]) == 2);
printf("%d\n", knapsack(C, N, W));
}
return 0;
}