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) =
 { -INF                                   , if w < 0
 { -INF                                   , 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], k); } 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[m] << "種不同的組合方式"; }

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

消極的方法：增加表格維度，以記錄物品個數。計算完畢之後，搜尋表格，窮舉物品個數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) =
 { -INF                                   , if n < 0
 { -INF                                   , if w < 0
 { -INF                                   , 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)); // -INF 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) =
 { +INF                                   , 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)); // +INF 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; }

【待補文字】

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

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/ε) DP 算出一個近似解，誤差範圍在精確解的ε倍以下。
解的好壞  端看 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(NlogM ⋅ W)，空間複雜度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]; }

演算法

http://www.cnblogs.com/GXZC/archive/2013/01/08/2851153.html

http://morris821028.github.io/2016/12/18/jg-20008/

各個同餘系分開處理，實施凸包優化，斜率皆是一，可視作deque優化。時間複雜度O(NW)。

各種相關問題

能否湊得某個價位（Money Changing Problem）
湊得某個價位的湊法總共幾種（Coin Change Problem）
湊得某個價位的最少（多）錢幣用量（Change-Making Problem）
湊得某個價位的最少（多）錢幣種類
所有無法湊得的價位當中，最大的價位（Frobenius Number）
所有無法湊得的價位總共幾種
限制錢幣用量，求得Frobenius Number加一（Postage Stamp Problem）

能否湊得某個價位（Money Changing Problem）

給定許多種不同面額的錢幣，能否湊得某個價位？每種面額的錢幣都無限供應，一定夠用。

Money Changing Problem其實就是Unbounded Knapsack Problem的變形：物品變成錢幣，物品重量變成面額，物品價值變成「湊得到、湊不到」兩種情況，累計價值的方式從加法運算變成OR運算。

唯一要小心的是：表格的初始值，把0元設定為可以湊到；但是正常情況下，是無法湊到0元的。

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

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

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

UVa 10306 10898 10261

湊得某個價位的湊法總共幾種（Coin Change Problem）

將OR運算改為加法運算罷了。

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

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

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

UVa 147 357 674 10313 430

湊得某個價位的最少錢幣用量（Change-Making Problem）

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

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

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

湊得某個價位的最少錢幣用量（Change-Making Problem）

當各種錢幣的面額有特別的關係時，有速度很快的Greedy演算法，詳細情形請參考Change-Making Problem。

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

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

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

UVa 242 10032 10690 10930

能否湊得某個價位，但是錢幣限量供應！

儘管可以直接套用bounded knapsack problem，但是事實上有一個比較簡潔的Greedy演算法 ：節省錢幣用量的前提下，盡量湊出各種價位。

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

UVa 233 711

所有無法湊得的價位當中，最大的價位（Frobenius Number）

Sebastian Böcker, Zsuzsanna Lipták. A Fast and Simple Algorithm for the Money Changing Problem. Algorithmica, 2007, 48, 413-432.

結合同餘理論、DP、Greedy，時間複雜度O(N⋅a1)，N為面額種類數，a1是最小的錢幣面額。

這個演算法也可以同時解決Money Changing Problem。

【待補文字】

限制錢幣用量，求得Frobenius Number加一（Postage Stamp Problem）

【待補文字】

找錢問題

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

演算法（Cashier's Algorithm）

演算法非常直覺。填答案的原則：先找給你面額較高的硬幣。

時間複雜度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 用貪心法是對的。
正確湊得 M 的最少錢幣用量為 (b1, b2, ..., bn)，稱呼為正確湊法 b 或者 b(M)。
貪心湊得 M 的最少錢幣用量為 (g1, g2, ..., gn)，稱呼為貪心湊法 g 或者 g(M)。

【性質甲】正確湊法有最佳子結構（包含關係）
若湊法 x 已經是最佳解，
則比 x 小的 y 統統都是最佳解（x >= y，每一個對應項都是大於等於）。
最短路徑截一段還是最短路徑的意思。

【性質乙】貪心湊法是嚴格遞增函數（字典順序關係）
貪心湊法當中，價錢較大的湊法，字典順序會大於價位較小的湊法。
（以高項次代表高位數。）
也就是說 g(X) 函數嚴格遞增，而 b(1 ~ M-1) = g(1 ~ M-1) 也是嚴格遞增。

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

【證明開始】
令 s 是 b(M) 最小的非零項索引值，t 是 b(M) 最大的非零項索引值。
也就是 b(M) = (0, ... , 0, bs, ... , bt, 0, ... , 0)，
bs 與 bt 都大於零，bs 的左邊都是零，bt 的右邊都是零。

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

【證明步驟二】M 之上限
正確的湊 M 不會用到 ct+1，正確的湊 (M - cs) 當然也不會用到 ct+1。【性質甲】
湊 (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(ct+1 -1) >= g(M - cs)，如果 g(M) 是對的湊法。【性質乙】
但是事實上 g(M) 是不對的，所以只好改成相似的：
b(M) > g(ct+1 - 1) >= b(M - cs)

【步驟三補充】證明 b(M) > g(ct+1 - 1 - ct) 在第 t 項加一
因為 b(M - ct) = g(M - ct)   >   b(ct+1 - 1 - ct) = g(ct+1 - 1 - ct)
剛好 ct 是最大的非零項，所以會滿足【逆向性質甲】，故在第 t 項加一即得證。
剛好 ct 是最大的非零項，也滿足貪心湊法的規則，
所以 g(ct+1 - 1 - ct) 在第 t 項加一，就正是 g(ct+1 - 1) 了。

【證明步驟四】
b(M) 與 b(M - cs) 幾乎一樣。【性質甲】【M的前提】

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

g(ct+1 - 1) 被夾在中間，根據字典順序關係【性質乙】，從第 s 項以上都是確定值。
反過來說，求出 g(ct+1 - 1)，就可以嘗試推理出 b(M) 和 b(M - cs) 的值。

【演算法】
M = +oo
for i = 1 to n
    算 g(ci+1 - 1) = b(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）
N個不同重量物品，M個不同耐重箱子，用最少箱子裝所有物品（Bin Packing 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<N; ++k) { // 暫時去除派系k， // 算出剩餘派系的投票情況種類數目。 memset(c, 0, sizeof(c)); c[0] = 1; for (int i=0; i<N; ++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<N; ++i) cout << i << "派系的BPI是" << float(power[i]) / sum; }

UVa 430 435