knapsack problem

將一群物品儘量塞進背包裡面，令背包裡面的物品總價值最高。背包沒有容量限制，無論物品是什麼形狀大小，都能塞進背包；但是背包有重量限制，如果物品太重，就會撐破背包。

以數學術語來說，背包問題就是選擇一個最理想的物品子集合，在符合重量限制的前提下、求得最大的利益！

背包問題有很多變形，接下來將會一一介紹。

fractional knapsack problem

fractional是「分數」的意思。一個物品可以切下一部分、只取幾分之幾放進背包。

我們很容易就可以制定一個greedy策略：價值與重量的比值最高的物品，優先放進背包。

總是用當下最好的物品填滿背包空隙，最後沒有留下任何空隙。每一份背包空間，都是最有價值的物品，就算是交換物品也無法增加總價值──顯然是最佳解。

時間複雜度O(N)。N是物品數量。

0/1 knapsack problem

「0/1」的意思是：每種物品只會放進背包零個或一個。一個物品要嘛整個不放進背包、要嘛整個放進背包。物品無法切割。

大家看到這個問題，第一個直覺通常是貪心法：優先挑選價值最高的物品。然而，價值高的物品，放進背包之後，有可能留下很大的空隙，浪費背包耐重量；反而是狂塞一些零零碎碎的不值錢東西，才能獲得最多的利益。

聰明的人會想：優先挑選價值與重量比值最大的物品。不過這個方法也有問題，仍然有可能出現方才提到的現象。你能舉例嗎？這有助於了解0/1背包問題的關鍵點。

0/1背包問題的關鍵點，在於如何有效利用背包的剩餘重量，找出最好的物品組合方式。

0/1背包問題是經典的NP-complete問題，無法快速求得精確解，只能折衷求得近似解。然而，當數值範圍不大時，得以用動態規劃快速求得精確解。

本篇文章打算藉由0/1背包問題的各種細節，介紹動態規劃的各種技巧。大綱如下：

讓背包裡面的物品總價值最大
讓背包裡面的物品總價值最小（背包不放東西就好了，沒有什麼好討論的。）
此時背包裡面放了哪些物品
此時背包裡面的物品有哪些不同的組合方式
此時背包裡面的物品有幾種不同的組合方式
此時背包裡面的物品盡量最少（多）個
此時背包裡面的物品總重量，最少是多少、最多是多少

UVa 431 624 990 10130 10819 10980

讓背包裡面的物品總價值最大（一）

窮舉法是最基本的方法。針對全部物品，窮舉所有子集合，找出物品總重量符合限制、物品總價值最大的子集合。

所有的子集合總共O(2ᴺ)個，驗證一個子集合需時O(N)，時間複雜度O(2ᴺ N)。N是物品的數量。

物品的編號順序是無所謂的。預先按照重量（或者是價值）排序所有物品，可以大幅減少計算時間。

讓背包裡面的物品總價值最大（二）

動態規劃是比較有效率的方法。分割問題的方式很簡單：對某一件物品來說，我們可以選擇放或不放；然後移去這件物品，縮小問題範疇。

一件物品不放進背包，背包價值不變、背包耐重不變；一件物品放進背包，背包價值上升、背包耐重下降。遞迴公式為：

c(n, w) = max( c(n-1, w), c(n-1, w-weight[n]) + cost[n] )
               ^^^^^^^^^  ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
               不放 -> 0            有放 -> 1

n：第0個到第n個物品要放進背包內。
w：背包耐重限制。
c(n, w)：只有第0個到第n個物品，耐重限制為w，此時的背包問題答案。
weight[n]：第n個物品的重量。
cost[n]：第n個物品的價值。

仔細考慮邊界條件，例如耐重不足的情況、沒有物品的情況：

c(n, w) =
 ⎧ -∞                                     , if w < 0
 ⎪ -∞                                     , if n < 0
 ⎨ 0                                      , if n = 0 and w ≥ 0
 ⎪ max( c(n-1, w),                        , if n > 0 and w ≥ 0
 ⎩      c(n-1, w-weight[n]) + cost[n] )

避免存取負的物品、負的耐重：

c(n, w) =
 ⎧ 0                                      , if n = 0
 ⎪ c(n-1, w)                              , if n > 0
 ⎨                                          and w-weight[n] < 0
 ⎪ max( c(n-1, w),                        , if n > 0
 ⎩      c(n-1, w-weight[n]) + cost[n] )     and w-weight[n] ≥ 0

const int N = 100; // 物品總數上限 const int W = 100000; // 背包耐重上限 //（可以使用物品的總重量作為此值） int cost[N], weight[N]; // 物品的價值與重量 int c[N + 1][W + 1]; // DP表格 // n為物品個數，w為背包耐重限制。 int knapsack(int n, int w) { if (w < 0) return -1e9; // 耐重能力不足，故只能不放。 if (n == 0) return 0; // 沒有物品時，就沒有cost。 // memoization，直接讀取記憶體的答案。 if (c[n][w]) return c[n][w]; // 遞迴求得小問題的答案 return c[n][w] = max( knapsack(n-1, w-weight[n]) + cost[n], knapsack(n-1, w) ); } const int N = 100, W = 100000; int cost[N], weight[N]; int c[N + 1][W + 1]; void knapsack(int n, int w) { memset(c, 0, sizeof(c)); for (int i = 0; i < n; ++i) // 窮舉每種物品 for (int j = 0; j <= w; ++j)// 窮舉每種重量 if (j - weight[i] < 0) // 耐重能力不足，故只能不放。 c[i+1][j] = c[i][j]; else // 耐重能力足夠，可以放或不放。 c[i+1][j] = max( c[i][j], c[i][j - weight[i]] + cost[i] ); cout << "最高的價值為" << c[n][w]; }

仔細觀察計算順序與表格，每次計算只需要上方和左上方的格子。我們可以重複利用記憶體，建立一條陣列就夠了；不過計算順序要改成由陣列後端開始，才不會覆蓋左上方的格子。

const int N = 100, W = 100000; int cost[N], weight[N]; int c[W + 1]; // 一條陣列就夠了 void knapsack(int n, int w) { memset(c, 0, sizeof(c)); for (int i = 0; i < n; ++i) for (int j = w; j - weight[i] >= 0; --j) // 由後往前 c[j] = max(c[j], c[j - weight[i]] + cost[i]); cout << "最高的價值為" << c[w]; } const int N = 100, W = 100000; // 物品的價值與重量，合併成一個物件，讓人容易理解。 struct Item {int cost, weight;} items[N]; int c[W + 1]; void knapsack(int n, int w) { memset(c, 0, sizeof(c)); for (int i = 0; i < n; ++i) { int weight = items[i].weight; int cost = items[i].cost; for (int j = w; j - weight >= 0; --j) c[j] = max(c[j], c[j - weight] + cost); } cout << "最高的價值為" << c[w]; }

時間複雜度O(NW)，空間複雜度O(W)。N是物品數量，W是背包重量限制。

時間複雜度包含了與輸入資料數量無關的變數W。按照定義，時間複雜度不是多項式時間──儘管它看起來是多項式。

此時背包裡面放了哪些物品

建立一個二維陣列，記錄每一個問題的答案，是由哪個子問題推導出來的。每個問題只有「放」或「不放」兩種情形。

這段程式碼只能找出其中一種組合方式，是字典順序最小的組合方式。只是列印順序剛好前後顛倒。

const int N = 100, W = 100000; int cost[N], weight[N]; int c[W + 1]; bool p[N][W + 1]; // 記錄放還是不放，false為不放，true為放。 void knapsack(int n, int w) { memset(c, 0, sizeof(c)); memset(p, false, sizeof(p)); // 初始化為false for (int i = 0; i < n; ++i) for (int j = w; j >= weight[i]; --j) if (c[j - weight[i]] + cost[i] > c[j]) { c[j] = c[j - weight[i]] + cost[i]; p[i][j] = true; // 有放 } cout << "最高的價值為" << c[w]; // 往回逆推，求出背包內的所有物品。 for (int i = n-1, j = w; i >= 0; --i) if (p[i][j]) // 背包有該物品 { cout << "背包裡面有第" << i << "個物品"; j -= weight[i]; } }

最原始的二維表格，亦足以判斷「放」或「不放」。程式碼稍嫌冗長，參考看看就好。

const int N = 100, W = 100000; int cost[N], weight[N]; int c[N + 1][W + 1]; // 足以判斷放或不放 void knapsack(int n, int w) { memset(c, 0, sizeof(c)); for (int i = 0; i < n; ++i) for (int j = 0; j <= w; ++j) if (j - weight[i] < 0) // 耐重能力不足，故只能不放。 c[i+1][j] = c[i][j]; else/* if (j - weight[i] >= 0)*/ // 耐重能力足夠，可以放或不放。 c[i+1][j] = max( c[i][j], c[i][j - weight[i]] + cost[i] ); cout << "最高的價值為" << c[n][w]; // 往回逆推，求出背包內的所有物品。 for (int i = n-1, j = w; i >= 0; --i) // 背包可以擁有該物品 if (j - weight[i] >= 0 && c[i+1][j] == c[i][j - weight[i]] + cost[j]) { cout << "背包裡面有第" << i << "個物品"; j -= weight[i]; } }

此時背包裡面的物品有哪些不同的組合方式

backtracking，窮舉所有組合方式。時間複雜度O(NA)，A是組合方式數量。

const int N = 100, W = 100000; int cost[N], weight[N]; int c[W + 1]; int p[N][W + 1]; // 0為不放，1為放，2為放與不放都可以。 void knapsack(int n, int w) { memset(c, 0, sizeof(c)); memset(p, 0, sizeof(p)); for (int i = 0; i < n; ++i) for (int j = w; j >= weight[i]; --j) // 不放比較好 if (c[j - weight[i]] + cost[i] < c[j]) { p[i][j] = 0; } // 放了比較好 else if (c[j - weight[i]] + cost[i] > c[j]) { c[j] = c[j - weight[i]] + cost[i]; p[i][j] = 1; } // 可放可不放 else/* if (c[j - weight[i]] + cost[i] == c[j])*/ { // c[j] = c[j - weight[i]] + cost[i]; p[i][j] = 2; } cout << "最高的價值為" << c[w]; // 往回逆推，求出背包內的所有物品。 find_path(n-1, c[w], 0); } int output[N]; void find_path(int n, int w, int k) { if (n < 0) // 找完了 { for (int i=0; i<k; ++i) cout << output[i]; return; } // 不放比較好：背包裡面沒有第n個物品 if (p[n][w] == 0) { find_path(n-1, w, k); } // 放了比較好：背包裡面有第n個物品 else if (p[n][w] == 1) { output[k] = n; find_path(n-1, w-weight[n], k+1); } // 可放可不放 else if (p[n][w] == 2) { // 背包裡面有第n個物品 output[k] = n; find_path(n-1, w-weight[n], k+1); // 背包裡面沒有第n個物品 find_path(n-1, w, k); } }

此時背包裡面的物品總共幾種不同的組合方式

每當遇到放與不放都沒有差別的時候，就表示遇到不同的組合方式，必須計數。

const int N = 100, W = 100000; int cost[N], weight[N]; int c[W + 1]; int way[W + 1]; // 記錄物品組合方式總共幾種 void knapsack(int n, int w) { memset(c, 0, sizeof(c)); memset(way, 0, sizeof(way)); way[0] = 1; for (int i = n-1; i >= 0; --i) for (int j = w; j >= weight[i]; --j) // 不放比較好 if (c[j - weight[i]] + cost[i] < c[j]) { // way[j] = way[j]; } // 放了比較好 else if (c[j - weight[i]] + cost[i] > c[j]) { c[j] = c[j - weight[i]] + cost[i]; way[j] = way[j - weight[i]]; } // 可放可不放 else/* if (c[j - weight[i]] + cost[i] == c[j])*/ { // c[j] = c[j - weight[i]] + cost[i]; way[j] = way[j] + way[j - weight[i]]; } cout << "最高的價值為" << c[w]; cout << "此時背包裡面的物品"; cout << "有" << way[w] << "種不同的組合方式"; }

此時背包裡面的物品盡量最少（多）個

消極的方法：增加表格維度，以記錄物品個數。計算完畢之後，搜尋表格，窮舉物品個數m，找到物品總價值最小的。

c(n, w, m) = max( c(n-1, w-weight[n], m-1) + cost[n],
                  c(n-1, w, m) )

m：放進背包的物品個數。

積極的方法：在計算過程當中，同步記錄背包裡面放了多少個物品。遇到放與不放都沒有差別的時候，就用物品的個數來決定要不要放，採用物品較少的方式。

附帶一提，這個方法也能找出此時背包裡面的物品總重量，最少是多少、最多是多少。

const int N = 100, W = 100000; int cost[N], weight[N]; int c[W + 1]; int m[W + 1]; // 同步記錄放了幾個物品 void knapsack(int n, int w) { memset(c, 0, sizeof(c)); memset(m, 0, sizeof(m)); for (int i = 0; i < n; ++i) for (int j = w; j - weight[i] >= 0; --j) // 放了比較好 if (c[j - weight[i]] + cost[i] > c[j]) { c[j] = c[j - weight[i]] + cost[i]; m[j] = m[j - weight[i]] + 1; } // 可放可不放 else if (c[j - weight[i]] + cost[i] == c[j]) { // 物品越少越好。 // 如果放了之後物品比較少，那就放了比較好。 if (m[j - weight[i]] + 1 < m[j]) { // c[j] = c[j - weight[i]] + cost[i]; m[j] = m[j - weight[i]] + 1; } } cout << "最高的價值為" << c[w]; } const int N = 100, W = 100000; int cost[N], weight[N]; int c[W + 1]; int m[W + 1]; // 同步記錄放了幾個物品 void knapsack(int n, int w) { memset(c, 0, sizeof(c)); memset(m, 0, sizeof(m)); for (int i = 0; i < n; ++i) for (int j = w; j - weight[i] >= 0; --j) // 把判斷式合併成一行 if (c[j - weight[i]] + cost[i] > c[j] || (c[j - weight[i]] + cost[i] == c[j] && m[j - weight[i]] + 1 < m[j])) { c[j] = c[j - weight[i]] + cost[i]; m[j] = m[j - weight[i]] + 1; } cout << "最高的價值為" << c[w]; }

此時背包裡面的物品總重量，最少是多少、最多是多少

計算完畢之後，搜尋表格，找到所有最佳解的位置，取物品總重量最小的。但是無法求出物品總重量最多是多少。

const int N = 100, W = 100000; int cost[N], weight[N]; int c[W + 1]; void knapsack(int n, int w) { memset(c, 0, sizeof(c)); for (int i=0; i<n; ++i) for (int j=w; j - weight[i] >= 0; --j) c[j] = max(c[j], c[j - weight[i]] + cost[i]); cout << "最高的價值為" << c[w]; // 往左搜尋最佳解的邊界 while (w-1 >= 0 && c[w-1] == c[w]) w--; cout << "物品總重量最少是" << w; }

讓背包裡面的物品總價值最大（三）

回到原始問題。遞迴公式其實還有許多種設計方式。

先前我們遞歸「物品編號」暨「背包耐重」，其實也可以改為遞歸「物品編號」暨「物品總重量」。

c(n, w) =
 ⎧ -∞                                     , if n < 0
 ⎪ -∞                                     , if w < 0
 ⎪ -∞                                     , if n = 0 and w ≠ 0
 ⎨                                                   ^^^^^^^^^
 ⎪ 0                                      , if n = 0 and w = 0
 ⎪                                                   ^^^^^^^^^
 ⎪ max( c(n-1, w),                        , if n > 0
 ⎩      c(n-1, w-weight[n]) + cost[n] )

n：第0個到第n個物品要放進背包內。
w：放進背包內的物品總重量！
c(n, w)：只有第0個到第n個物品，背包內的物品總重量為w，此時的背包問題答案！
weight[n]：第n個物品的重量。
cost[n]：第n個物品的價值。

時間複雜度O(NW)，空間複雜度O(W)。N是物品數量，W是物品總重量。

計算完畢之後，搜尋表格，找到所有最佳解的位置；另外也很容易找到此時背包裡面的物品總重量，最少是多少、最多是多少。大可不必使用輔助表格。

const int N = 100, W = 100000; int cost[N], weight[N]; int c[W + 1]; void knapsack(int n, int w) { memset(c, 0x80, sizeof(c)); // -∞ c[0] = 0; for (int i=0; i<n; ++i) for (int j=w; j - weight[i] >= 0; --j) c[j] = max(c[j], c[j - weight[i]] + cost[i]); // 搜尋最佳解 int bestw = 0; for (int i = 1; i < w; ++i) if (c[i] > c[bestw]) bestw = i; cout << "最高的價值為" << c[bestw]; // 搜尋總重量 for (int minw = 0; minw < w; ++minw) if (c[minw] == c[bestw]) { cout << "物品總重量最少是" << minw; break; } // 搜尋總重量 for (int maxw = w; maxw >= 0; --maxw) if (c[maxw] == c[bestw]) { cout << "物品總重量最多是" << maxw; break; } }

讓背包裡面的物品總價值最大（四）

一開始我們遞歸「物品編號」暨「背包耐重」，讓「物品總價值」越大越好。最後直接從表格取得答案。

然後我們遞歸「物品編號」暨「物品總重量」，讓「物品總價值」越大越好。最後搜尋表格，找到物品總價值最大的答案。

其實也可以遞歸「物品編號」暨「物品總價值」，讓「物品總重量」越小越好。最後搜尋表格，找到符合背包重量限制的答案。

w(n, c) =
 ⎧ +∞                                     , if n < 0 or  c < 0
 ⎨ 0                                      , if n = 0 and c = 0
 ⎪ min( w(n-1, c),                        , if n > 0
 ⎩      w(n-1, c-cost[n]) + weight[n] )

n：第0個到第n個物品要放進背包內。
w：放進背包內的物品總重量！
c(n, w)：只有第0個到第n個物品，背包內的物品總重量為w，此時的背包問題答案！
weight[n]：第n個物品的重量。
cost[n]：第n個物品的價值。

時間複雜度O(NC)，空間複雜度O(C)。N是物品數量，C是物品價值總和。

const int N = 100, C = 100000; int cost[N], weight[N]; int w[C + 1]; void knapsack(int n, int W) { memset(w, 0x7f, sizeof(w)); // +∞ w[0] = 0; for (int i=0; i<n; ++i) for (int j=C; j - cost[i] >= 0; --j) w[j] = min(w[j], w[j - cost[i]] + weight[i]); // 搜尋最佳解 int c = C; while (w[c] > W) c--; cout << "最高的價值為" << c; }

讓背包裡面的物品總價值最大（五）

物品放進背包時，按照物品編號順序來放。每一種物品都可能是最後一個放進背包的物品。

c(n, w) = max(
   0 ,                                 都不放
   c(0, w-weight[0]) + cost[0] ,       最後是放第0個物品
   c(1, w-weight[1]) + cost[1] ,       最後是放第1個物品
   ... ,                               ...
   c(n-1, w-weight[n-1]) + cost[n-1]   最後是放第n-1個物品
)

n：第0個到第n個物品要放進背包內。
w：背包負重上限。
c(n, w)：只有第0個到第n個物品，負重限制為w，此時的背包問題答案。
weight[n]：第n個物品的重量。
cost[n]：第n個物品的價值。

時間複雜度O(NNW)，空間複雜度O(NW)。N是物品數量，W是物品總重量。

const int N = 100, W = 100000; int cost[N], weight[N]; int c[N + 1][W + 1]; int knapsack(int n, int w) { if (w < 0) return -1e9; if (n == 0) return 0; if (c[n][w]) return c[n][w]; int v = 0; for (int i=0; i<n; ++i) // 每個物品都試試看 v = max(v, knapsack(i, w-weight[i]) + cost[i]); return c[n][w] = v; }

讓背包裡面的物品總價值最大（六）

Simple and Faster Algorithms for Knapsack
https://epubs.siam.org/doi/epdf/10.1137/1.9781611977936.6

correct with high probability
https://en.wikipedia.org/wiki/With_high_probability

c[n][w] 每一層只計算一部分：
c[i][(i/n)W - sqrt(i)Wₘₐₓ] 到 c[i][(i/n)W + sqrt(i)Wₘₐₓ]
其他部分直接當作是0。
時間複雜度降為O(N N sqrt(Wₘₐₓ))，Wₘₐₓ是物品重量最大值。
仍有非常高的機率可以得到正確答案。

讓背包裡面的物品總價值最大（七）

polynomial-time approximation scheme
http://www.cse.cuhk.edu.hk/~chi/csc5160-2008/notes/L17-PTAS.pdf

cost 超級大，沒辦法用DP解的時候，
把每個物品的 cost 硬是降下去：
c' = ceil(c / maxc ⋅ n / ε)
就可以用 O(nc') = O(nnn/ε)
算出一個近似解，誤差範圍在精確解的ε倍以下。
解的好壞，端看 cost 降少還是降多。

讓背包裡面的物品總價值最大（八）

背包問題是「最佳化」問題。我們可以用各種最佳化演算法，快速求得近似解，例如「linear programming一次規劃」、「genetic algorithm基因演算法」。不過這已經脫離本篇文章的主旨了，就請讀者自行研究吧！

UVa 10715

總結

一、建立輔助表格，處理附加的條件。
二、增加表格維度，處理更多的條件。
三、最佳解可能有許多個，搜尋表格以找到所有最佳解。
四、遞迴公式有著許多種設計策略。
五、遞迴公式有時能夠順手處理附加的條件，不需輔助表格。
六、調整數值規模，得到近似解。

無限背包問題

物品有許多種類，每一種物品都無限量供應的背包問題。

UVa 10465

演算法

分割問題的方式可以仿照0/1背包問題。0/1背包問題是一個物品的去留；無限背包問題則是一種物品的去留。考慮一種物品的各種用量：

c(n, w) = max(
   c(n-1, w - weight[n] ⋅ 0) + cost[n]     ,   用去零個第n種物品
   c(n-1, w - weight[n] ⋅ 1) + cost[n] ⋅ 1 ,   用去一個第n種物品
   c(n-1, w - weight[n] ⋅ 2) + cost[n] ⋅ 2 ,   用去兩個第n種物品
   ... ,                                       ...
)

n：第0種到第n種物品要放進背包內。
w：背包耐重限制。
c(n, w)：只有第0種到第n種物品，耐重限制為w，此時的背包問題答案。
weight[n]：第n種物品的重量。
cost[n]：第n種物品的價值。

時間複雜度O(NWW)，空間複雜度O(W)。

演算法

更好的方式，其實仍是一個物品的去留：

c(n, w) = max( c(n-1, w), c(n, w-weight[n]) + cost[n] )
                            ^^
                            只有這裡不同，因為物品無限量供應。

時間複雜度降為O(NW)，空間複雜度O(W)。

const int N = 100, W = 100000; int cost[N], weight[N]; int c[W + 1]; void knapsack(int n, int w) { memset(c, 0, sizeof(c)); for (int i=0; i<n; ++i) for (int j = weight[i]; j <= w; ++j) c[j] = max(c[j], c[j - weight[i]] + cost[i]); cout << "最高的價值為" << c[w]; }

UVa 10898

有限背包問題

物品有許多種類，每一種物品都是限量供應的背包問題。

演算法

仿照無限背包問題，考慮每一種物品的用量：

c(n, w) = max(
   c(n-1, w - weight[n] ⋅ 0) + cost[n] ⋅ 0 ,   用去零個第n種物品
   c(n-1, w - weight[n] ⋅ 1) + cost[n] ⋅ 1 ,   用去一個第n種物品
   ... ,                                       ...
   c(n-1, w - weight[n] ⋅ number[n])           用去number[n]個第n種物品
      + cost[n] ⋅ number[n]
)

n：第0種到第n種物品要放進背包內。
w：背包耐重限制。
c(n, w)：只有第0種到第n種物品，耐重限制為w，此時的背包問題答案。
weight[n]：第n種物品的重量。
cost[n]：第n種物品的價值。
number[n]：第n種物品的數量。

時間複雜度O(NWM)，空間複雜度O(W)。M是物品數量最大值（不是總和）。

UVa 10086

演算法

scaling method。同種類的M個物品，實施二進位分解，重捆成1、2、4、8、……、2ᵏ、M - 2ᵏ個物品，一共⌈logM⌉捆。這些捆的0/1組合，可以湊出各種數量的物品。

一捆視作一個物品，直接套用0/1背包問題，物品數量從N變成O(NlogM)。

時間複雜度O(NWlogM)，空間複雜度O(W)。

const int N = 100, W = 100000; int cost[N], weight[N], number[N]; int c[W + 1]; void knapsack(int n, int w) { for (int i = 0; i < n; ++i) { int num = min(number[i], w / weight[i]); for (int k = 1; num > 0; k *= 2) { if (k > num) k = num; num -= k; for (int j = w; j >= weight[i] * k; --j) c[j] = max(c[j], c[j - weight[i] * k] + cost[i] * k); } } cout << "最高的價值為" << c[w]; }

演算法

各種餘數分開處理，實施convex hull加速，斜率皆是一，可視作deque加速。時間複雜度O(NW)。

coin problem

給定許多種不同面額的錢幣。能否湊得某個價位？共有幾種湊法？需要幾個錢幣？諸如此類的計數問題。

各種相關問題

湊得哪些價位。　　　　　　　　（money changing problem）
湊得某個價位，是否可行。
湊得某個價位，湊法數目。　　　（coin change problem）
湊得某個價位，錢幣用量盡量少。（change-making problem）
湊得某個價位，錢幣種類盡量少。

money changing problem

湊錢問題。給定許多種不同面額的錢幣，可以湊得哪些價位？

能否湊得某個價位

unbounded knapsack problem的變形：物品變成錢幣，物品重量變成面額，物品價值變成「湊得到、湊不到」兩種情況，累計價值的方式從加法運算變成OR運算。

唯一要小心的是：表格的初始值，把0元設定為可以湊到。

時間複雜度O(NW)。N是錢幣種類，W是價位。

c(n, w) = c(n-1, w) or c(n, w-price[n])
          ^^^^^^^^^    ^^^^^^^^^^^^^^^^
         不用這種錢幣    用去一個錢幣

n：用第0種到第n種錢幣來湊得價位。
w：欲湊得的價位值。
c(n, w)：用第0種到第n種錢幣湊得價位w的湊法數目。
price[n]：第n種錢幣的面額大小。

// 錢幣面額，順序可隨意。 int price[5] = {5, 2, 6, 11, 17}; // -1代表沒計算過。一開始必須全部初始化為-1。 // 大於等於0代表該問題有計算過。 int c[5][1000+1]; bool change(int n, int w) { if (n < 0 || w < 0) return 0; // 0代表false if (w == 0) return 1; // 1代表true if (c[n][w] != -1) return c[n][w]; return c[n][w] = change(n-1, w) | change(n, w - price[n]); } int price[5] = {5, 2, 6, 11, 17}; bool c[1000+1]; // 看看 {5, 2, 6, 11, 17} 這些面額湊不湊得到價位 w void change(int w) { memset(c, false, sizeof(c)); c[0] = true; // 依序加入各種面額 for (int i = 0; i < 5; ++i) // 由低價位逐步到高價位 for (int j = price[i]; j <= w; ++j) // 湊、湊、湊 c[j] |= c[j-price[i]]; if (c[w]) cout << "湊得到"; else cout << "湊不到"; }

UVa 10306 10898 10261

能否湊得某個價位（錢幣限量供應）

儘管可以直接套用bounded knapsack problem，但是事實上存在簡潔的greedy演算法 ：節約錢幣用量，盡量湊出各種價位。

時間複雜度O(NW)。N是錢幣種類，W是價位。

int price[5] = {5, 2, 6, 11, 17}; int number[5] = {4, 5, 5, 3, 2}; // 各種錢幣的供應數量 bool c[1000+1]; void change(int w) { memset(c, false, sizeof(c)); c[0] = true; for (int i = 0; i < 5; ++i) // 各種餘數分開處理 for (int k = 0; k < price[i]; ++k) { int left = 0; // 沒有彈藥 // 由低價位到高價位 for (int j = k; j <= w; j += price[i]) // 先前的面額已能湊得，當前面額可以省著用。 if (c[j]) left = number[i]; // 補充彈藥 // 過去都無法湊得，一定要用目前面額硬湊。 else if (left > 0) { left--; // 用掉一個錢幣 c[j] = true; } } if (c[w]) cout << "湊得到"; else cout << "湊不到"; }

UVa 711 233

湊得哪些價位

搜尋表格，列出答案。時間複雜度O(NW)。

湊得幾種價位

搜尋表格，統計答案。時間複雜度O(NW)。

湊得幾種價位

進階解法是「各種餘數分開處理」與「最短路徑」。中文網路稱作「同余最短路」。

一、等差數列：考慮一種價位w。考慮第一種錢幣面額p₁。如果價位w可以用其餘面額湊得，那麼價位w+p₁、w+p₁+p₁、……也可以湊得，價位w-p₁、w-p₁-p₁、……不一定可以湊得。

二、餘數：方便起見，價位簡化為w (mod p₁)。然後利用最短路徑，找到可以湊得的最低價位。

三、p₁個點：0 (mod p₁)到p₁-1 (mod p₁)涵蓋所有價位。

四、p₁(N-1)條邊：考慮各種價位a。考慮其餘錢幣面額pᵢ。讓a + pᵢ = b變成a + pᵢ ≡ b (mod p₁)，對應到邊ab權重pᵢ。

五、單源最短路徑：起點是價位0，對應到點0 (mod p₁)。最短路徑長度，即是可以湊得的最低價位。

最後還得計算正確答案。令第i點的最短路徑長度是lᵢ。

一、無法湊得的價位當中，最大的價位：(lᵢ-p₁)取最大值。數學家稱作Frobenius number。

二、無法湊得的價位種類：(lᵢ-p₁)/p₁通通相加。

三、可以湊得的價位種類：無限多。如果指定了價位範圍，那麼運用減法即可。

時間複雜度O(V² + E) = O(p₁² + Np₁)或者O(V + ElogV) = O(Np₁logp₁)。N為錢幣種類，p₁是最小的錢幣面額。

luogu P3403 P2371

湊得幾種價位（錢幣限量供應）（postage stamp problem）

我沒有研究。

coin change problem

換錢問題。給定許多種不同面額的錢幣，能否湊得某個價位？又有幾種湊法？

湊得某個價位的湊法數目

OR運算改為加法運算罷了。時間複雜度O(NW)。

c(n, w) = c(n-1, w) + c(n, w-price[n])
          ^^^^^^^^^   ^^^^^^^^^^^^^^^^
         不用這種錢幣   用去一個錢幣

c(n, w)：用第0種到第n種錢幣湊得價位w的湊法數目。

int price[5] = {5, 2, 6, 11, 17}; int c[1000+1]; void change(int w) { memset(c, 0, sizeof(c)); c[0] = 1; for (int i = 0; i < 5; ++i) for (int j = price[i]; j <= w; ++j) c[j] += c[j-price[i]]; cout << "湊得價位" << w; cout << "湊法總共" << c[w] << "種"; }

UVa 147 357 674 10313 430

湊得某個價位的湊法數目

進階解法是「生成函數」。每種錢幣分別建立一個多項式。多項式連乘，W次方項的係數就是答案。時間複雜度O(NWlogW)。

面額為1的錢幣 (x⁰+x¹+x²+...)
面額為2的錢幣 (x⁰+x²+x⁴+...)
面額為3的錢幣 (x⁰+x³+x⁶+...)
     :

ln()、連乘化連加、exp()。時間複雜度降為O(WlogW)。

一、多項式ln()：心中推導，不必寫成程式碼。

二、多項式連加：最差的情況是每種面額通通都有。時間複雜度W/1 + W/2 + ... + W/W = O(WlogW)。

三、多項式exp()：時間複雜度O(WlogW)。

luogu P4389

change-making problem

找錢問題。你去商店買東西，你掏出了一張百元鈔票，買了一包23元的零食。櫃員須找錢給你，但是你希望櫃員找給你的硬幣數目越少越好，如此口袋會輕一點。那麼櫃員會給你幾個硬幣呢？

湊得某個價位的最少錢幣用量

c(n, w) = min( c(n-1, w) , c(n, w-price[n]) + 1 )
               ^^^^^^^^^   ^^^^^^^^^^^^^^^^^^^^
               保持一樣        用去一個錢幣

c(n, w)：用第0種到第n種錢幣湊得價位w，最少所需要的錢幣數量。

int price[5] = {5, 2, 6, 11, 17}; int c[1000+1]; void change(int w) { memset(c, 0x7f, sizeof(c)); c[0] = 0; for (int i = 0; i < 5; ++i) for (int j = price[i]; j <= w; ++j) c[j] = min(c[j], c[j-price[i]] + 1); cout << "湊得價位" << w; cout << "最少需（只）要" << c[w] << "個錢幣"; }

湊得某個價位的錢幣用量，有哪幾種可能性。

錢幣用量不多時，可以直接以int變數（充作32個元素的bitset）或long long變數（充作64個元素的bitset）作為一個bitset，利用位元運算求出所有可能性。

int price[5] = {5, 2, 6, 11, 17}; // 每一格都是一個bitset， // 記錄該價位可用幾個錢幣湊得，包含各種可能性。 long long c[1000]; void change(int w) { memset(c, 0, sizeof(c)); c[0] = 1; for (int i = 0; i < 5; ++i) for (int j = price[i]; j <= w; ++j) // 錢幣數量加一，每一種可能性都加一。 c[j] |= c[j-price[i]] << 1; for (int i = 1; i <= 63; ++i) if (c[w] & (1 << i)) cout << "用" << i << "個錢幣可湊得價位" << w; }

UVa 242 10032 10690 10930

湊得某個價位的最少錢幣用量（cashier's algorithm）

各種錢幣的面額有特殊關係時，存在簡易的greedy演算法。

填答案的原則：先找給你面額較高的硬幣。

時間複雜度O(N)，N是銅板種類。

int price[5] = {50, 20, 10, 4, 2}; // 面額由大到小排列 void cashier(int n) // n 是總共要找的錢。 { int c = 0; for (int i=0; i<5; ++i) while (n >= price[i]) { n -= price[i]; // 找了 price[i] 元 c++; } if (n != 0) cout << "找不出來"; else cout << "找了" << c << "個錢幣"; } int price[5] = {50, 20, 10, 4, 2}; void cashier(int n) { int c = 0; for (int i=0; i<5; ++i) { c += n / price[i]; n %= price[i]; } if (n != 0) cout << "找不出來"; else cout << "找了" << c << "個錢幣"; }

UVa 166

適用情況（Pearson's algorithm）

現實生活中，錢幣面額經過精心設定，可以安心使用cashier's algorithm。

不幸的是，並不是任意一種錢幣面額，都可以使用cashier's algorithm。想要使用cashier's algorithm，得先經過驗證才行：

一、各種價錢都能找，不會有找不出來的情況。
二、錢幣用量真的是最少的。

時間複雜度O(N³)。

【問題描述】
一組錢幣面額 (c1, c2, ..., cn)，面額大小順序 c1 < c2 < ... < cn。
找出不適用貪心法的最小價位 M。意即 1 ... M-1 使用貪心法結果正確。
正確湊得 X 的最少錢幣用量為 (b1, b2, ..., bn)，稱呼為正確湊法 b(X)。
貪心湊得 X 的最少錢幣用量為 (g1, g2, ..., gn)，稱呼為貪心湊法 g(X)。

【性質甲】正確湊法有最佳子結構（支配關係）
若湊法 (x1, x2, ..., xn) 已經是正確湊法，
則湊法 (y1, y2, ..., yn) <= (x1, x2, ..., xn)
通通都是（更低價位的）正確湊法。
（對應項皆小於等於。）

【性質乙】貪心湊法是嚴格遞增函數（字典順序關係）
貪心湊法總是由較大的面額開始湊。
g(A) < g(B) when A < B
高價位的貪心湊法，字典順序大於低價位的貪心湊法。
（以高項次代表高位數。）
也就是說 g(X) 嚴格遞增，
也就是說 (b(1) ... b(M-1)) = (g(1) ... g(M-1)) 也是嚴格遞增。

【性質丙】b(M) 與 g(M) 不相交
b(M) × g(M) = (0, 0, 0, ...., 0)
對應項不會同時有值。
因為拿掉這些錢幣，M 就可以更小，矛盾。
這個性質不會用到。

【證明開始】
令 s 是 b(M) 最小的非零項。bs 是錢幣用量。cs 是面額。
令 t 是 b(M) 最大的非零項。bt 是錢幣用量。ct 是面額。
意即 b(M) = (0, ... , 0, bs, ... , bt, 0, ... , 0)，
bs 與 bt 都大於零，bs 的左邊都是零，bt 的右邊都是零。

【證明步驟一】M 之下限
貪心湊法總是由較大的面額開始湊。
湊 M 出錯的時候，一定是拿了比 ct 更大的面額。
所以 M 至少會有 ct+1 那麼大。M ≥ ct+1。

【證明步驟二】M 之上限
正確湊法 b(M) 不會用到 ct+1，
正確湊法 b(M - cs) 也不會用到 ct+1。【性質甲】
貪心湊法 g(M - cs) 是正確湊法。【M的前提】
貪心湊法總是由較大的面額開始湊。
沒有用到 ct+1，表示 (M - cs) 太小了，所以 (M - cs) < ct+1。
（亦可得到 (M - ct) < ct+1 ，比較寬鬆，不會用到。）

【證明步驟三】觀察 (ct+1 - 1) 的湊法。上限下限夾擠。
M > (ct+1 - 1) ≥ (M - cs)　【步驟一二】
又如果 g(M) 是對的湊法：
g(M) > g(ct+1 - 1) ≥ g(M - cs)　【性質乙】
但是事實上 g(M) 是不對的湊法，所以只好改成相似的式子：
b(M) > g(ct+1 - 1) ≥ b(M - cs)

【步驟三補充】證明 b(M) > g(ct+1 - 1)
考慮 g(M - ct) = b(M - ct)
   > g(ct+1 - 1 - ct) = b(ct+1 - 1 - ct)　【步驟一】【性質乙】
剛好 t 是最大的非零項，套用【逆向性質甲】，
所以 b(M - ct) 在第 t 項加一，正是 b(M)。
剛好 t 是最大的非零項，滿足貪心湊法的規則，
所以 g(ct+1 - 1 - ct) 在第 t 項加一，正是 g(ct+1 - 1)。

【證明步驟四】第 s 項之後完全相同

      b(M)        = ( ..., 0 , gs    , ... , gt, 0 , ... )
    > g(ct+1 - 1) = ( ???, ? , gs - 1, ... , gt, 0 , ... )
    ≥ b(M - cs)   = ( ..., 0 , gs - 1, ... , gt, 0 , ... )

b(M) 與 b(M - cs) 第 s 項只差 1。【性質甲】【M的前提】
g(ct+1 - 1) 被夾在中間，
根據字典順序關係【性質乙】，第 s 項之後完全相同。
求出 g(ct+1 - 1)，就可以嘗試推理出 b(M) 和 b(M - cs)。

【演算法】
M = +∞
for i = 1 to n
    算 g(ci+1 - 1)
    for j = 1 to i     // 窮舉第 s 項的位置
        算 b(X)：讓 g(ci+1 - 1) 第 j-1 項以下都變成零，讓第 j 項加一。
        算 X
        算 g(X)
        if g(X) 與 b(X) 的錢幣用量相同（項次不同沒關係）
            X可以湊出正確值。不做任何事。
        else
            更新 M，M = min(M, X)。
return M

各種相關問題

一個數字集合，挑幾個數字，總和恰為零（subset sum problem）
一個數字集合，挑幾個數字，總和恰為整體總和的一半（partition problem）

通通可以套用0/1 knapsack problem的思維模式。

Banzhaf power index

有一項決策要投票表決，一人一票，不得投廢票，過半數贊成則通過，反之則否決。投票者由許多派系組成，各個派系都相當團結，同樣派系的人，要嘛全部都是投贊成票，要嘛全部都是投反對票。然而有些派系人多，有些派系人少，人多的派系能左右大局，人少的派系卻勢單力薄。於是產生一個問題：有能力對最終決策造成影響的是哪些派系？影響能力又是多少？

一個派系有能力對決策造成影響，是指所有派系都設定立場之後，此派系一旦改變立場，會馬上顛倒決策結果。換個觀點來看，此派系之外的所有派系都投完票之後，此派系若全數投贊成票，則會使決策順利通過，反之若全數投反對票，則會使決策無法通過。

Banzhaf power index的計算方式是這樣的：一個派系X的Banzhaf power index = 派系X影響決策的情況數目 ÷ (派系1影響決策的情況數目 + ... + 派系N影響決策的情況數目)。所有派系的Banzhaf power index的總和會是1。

藉由Banzhaf power index，可以看出各派系的實力，也可以看出投票表決是否公平。

1.
A派系9票、B派系9票、C派系7票、D派系3票、E派系1票、F派系1票。
總共投票數為30票。過半數之票數為16票。

2.
以A派系為例，A派系影響決策的情況，一共有16種：

   AB AC ABC ABD ABE ABF ACD ACE ACF
   ABDE ABDF ABEF ACDE ACDF ACEF ADEF

派系有出現，表示投贊成票；派系無出現，表示投反對票。
拿掉A則會逆轉決策結果。

3.
可以發現D派系、E派系、F派系，
完全無法介入結果，沒有任何影響力：

  | votes | power |  BPI
--+-------+-------+-------
A |   9   |  16   | 16/48
B |   9   |  16   | 16/48
C |   7   |  16   | 16/48
D |   3   |   0   |   0
E |   1   |   0   |   0
F |   1   |   0   |   0
--+-------+-------+--------
  |  30   |  48   |  1.0

計算一個派系影響決策的情況數目

甲、移除此派系。
乙、剩餘派系進行投票，並算出各種不同總票數之下的情況數目。
丙、搜尋靠近過半票數的情況，累計這些情況數目。

是partition problem的延伸應用。

時間複雜度O(N²S)，N是派系數目，S是總投票數，或者說是過半票數。

int w[6]; // 各種派系的人數 int c[(16-1) + 1]; // 算出0票到15票這些未過半數的情形 int power[6]; // 各派系影響決策結果的情況數目 int sum = 0; // power[]總和 void Banzhaf_power_index() { for (int k=0; k<6; ++k) { // 暫時去除派系k， // 算出剩餘派系的投票情況種類數目。 memset(c, 0, sizeof(c)); c[0] = 1; for (int i=0; i<6; ++i) if (i != k) for (int j=16-1; j>=w[i]; --j) c[j] += c[j-w[i]]; // 累計靠近過半票數的情況數目 power[k] = 0; for (int j=max(16-w[k], 0); j<16; ++j) power[k] += c[j]; sum += power[k]; } for (int i=0; i<6; ++i) cout << i << "派系的BPI是" << float(power[i]) / sum; }

UVa 430 435