作者 ｜ 劉潔
問題概述
一筆訂單最多可使用所含電影票數目張兌換券。換而言之，用戶選了幾個座位，最多便能使用幾張兌換券，兌換券有三個屬性，分別是：
面值（元）：在不支持補差的情況下，票價小于等于面值才可以使用
固定支付金額（元）：滿足兌換券的使用條件下，需要支付的錢。
補差（是 / 否）：如果支持補差，當票價大于面值時，還需要額外支付 （票價 - 面值）元
- 舉個栗子：小明有一張面值 50，固定支付 19 元且支持補差的兌換券。那么他能使用這張兌換券去購買票價小于等于 50 元的電影票，只需支付 19 元。因為支持補差，所以他能購買票價為 60 元（大于面值）的電影票，需支付（19 + （ 60 - 50））既 29 元。
我們問題是：用戶下了一筆訂單，訂單中有 x（根據業務場景，x <= 6）張電影票，y 張兌換券，從這 y 張兌換券中選擇不超過 x 張兌換券，使得該筆訂單的實際支付金額最少，如果有多種解決方案，那么根據以下優先級為用戶推薦選券的方案：
優先級 1: 選擇實際支付金額少的方案
優先級 2: 如果實際支付金額一致，則優先使用面值小的方案
- 原因：如果用戶想購買一張票價為 38 元的電影票，當前他有一張 40 元和一張 60 元的兌換券，任意使用一張兌換券能得到的實際支付金額都是 0 元，那么優先為用戶選擇 40 元的兌換券，這樣 60 元的兌換券就能服務于用戶的下一筆訂單，更能為用戶省錢。
- 優先級 3: 若面值大小也一致，則優先使用優惠券所在券包消耗券數目多的優惠券
- 優先級 4: 若消耗券數目一致，則優先使用過期時間早的優惠券
技術方案
方案一：貪心
具體步驟：排序
對票價從大到小排序，讓票價高的電影票優先選擇，目的就是為了金額大的電影票優先使用限制條件少（既面值大）的兌換券，讓券面值得到充分利用，每個票和券的組合都盡可能是最優解。
證明方法：舉反例法
很不幸，很快就找出一個反例推翻了這個方案，反例如圖所示
方案二：暴力枚舉
枚舉所有方案，從這所有方案中求出最優解，但是時間復雜度高達 C(y, x) * A(x, x) 也就是 O(n!)，若按照 1s 鐘計算機能運行 10^8 次計算這樣的標準，當 n = 13 的時候，需要超過 10s 才能得到答案，并且 n 每增加 1，時間就會擴大 n 倍。
解決方案三：二分圖最優匹配算法——KM 算法
km（Kuhn-Munkres）算法簡介
km 算法是一種二分圖最佳匹配算法，該算法主要用于解決一個經典的問題模型：完美婚姻問題。該問題的描述如下：n 個男生和 n 個女生相親，第 i 個男生和第 j 個女生在一起的幸福值是 val(i, j)，如何讓 n 個男生和 n 個女生完成一一配對，使得這個整體的總幸福值最大。我們的問題和完美婚姻問題模型有點相似，并且經過調研 km 算法時間復雜度是 n^3，km 算法有一個非常大的優點就是，他可以求出哪張券用于哪張電影票，適用于選座相關的業務場景。
km 算法落地（對 km 算法不熟悉的同學可以先瀏覽第三部分）
我們把兌換券看成男生，電影票看成女生，用兌換券 j 購買電影票 i 的花費是 -w(i, j)去建圖，如果兌換券 j 無法購買電影票 i，那么花費 w(i, j)設置為負無窮大，去構造一個二分圖嘗試求解，我們會遇到一些問題：
改造一：如何滿足 km 算法的使用條件？
因為 km 算法是用于求解二分圖的最佳匹配，也就是說二分圖必須存在最佳匹配才能使用 km 算法求解。存在最佳匹配的必要條件是：必須兩邊的點相同，而且至少存在一種匹配方案使得所有的點都被匹配。所以我們需要補點和補邊（補點和補邊也是使用 km 算法的常見的技巧）。補邊策略：將不存在的邊，權重設為-inf。補點策略：新增 x 張兌換券，第 y + i 張兌換券跟第 i 張電影票連邊，權值為電影票的原價，這樣一來可以保障把無窮大的結果排除在外，二來不需要再額外再計算使用原價購買的情況。
改造二：如何在多個解中求出滿足優先級的解？
我們可以把所有兌換券按照面值由小到大排序，如果面值一致，那么按照入賬時間從早到晚排序，如果入駐時間一致，按照過期時間由早到晚排序，簡而言之，把優先級高的券放在前面。枚舉數量 k，對前 k 個兌換券和所有的電影票加入 km 模型中，計算出最少花費，只有花費變得比之前更小才更新答案。這樣可以保證取得最少花費的同時，還能滿足優先級。還有一個好處是，如果后續 pm 對策略的優先級進行調整，那么我們可以更改最初的排序規則即可。但是時間復雜度此時變成了 n^4。
如圖所示，當 k 等于 2 的時候取得最優解，k=3 的時候有可能匹配到優先級低的券。
改造三、時間復雜度的優化
經過改造一和改造二的處理后，算法時間復雜度是：（x+y)^4 + y*logy（x 代表電影票張數，y 代表兌換券張數）
時間復雜度分析：經過補點操作后，二分圖兩邊的點都是 x + y 個。因為 km 算法的時間復雜度是 n ^ 3 次方，n 為二分圖單側的點的個數。所以當前的時間復雜度是 （x+y)^3 。為了處理匹配的優先級問題，我們對優惠券進行了優先級排序，時間復雜度是y*logy，在運行 km 算法的時候，枚舉了數量 k，所以總時間復雜度為（x+y)^4 + y*logy。
改造方法
具體步驟：對于每一張電影票，預處理出對于這張電影票優先級最高的 n（n 為當前的電影票張數）張，把這些兌換券去重，我們就能得到最多 nn 張兌換券。用著 nn 張兌換券代替原來的所有優惠券
- 時間復雜度（優化后，算法的時間復雜度跟優惠券數目無關，而跟電影票張數有關，目前的業務場景是，電影票最多不超過 4 張，所以該算法有較好的性能）：
- 預處理出x*x?張優惠券的時間復雜度：x^2 * y * logx(x 為電影票數目，y 為優惠券數目）
- 運行 km 算法求最優解的時間復雜度：((1 + x) * x)^4 + 2 * x^2 *logx(x 為電影票數目)
- 總時間復雜度：x^2 * y * logx? + ((1 + x) * x)^4 + 2 * x^2 *logx(x 為電影票數目，且 0 < x <= 4)
收益：
當用戶有 500 張兌換券（極限值時），能非常迅速的計算出最優策略，幾乎無延遲。
km 原理證明
前置知識
二分圖：又稱作二部圖，是圖論中的一種特殊模型。設 G=(V,E)是一個無向圖，如果頂點 V 可分割為兩個互不相交的子集(A,B)，并且圖中的每條邊（i，j）所關聯的兩個頂點 i 和 j 分別屬于這兩個不同的頂點集(i in A,j in B)，則稱圖 G 為一個二分圖。
匹配：在二分圖中，一個「匹配」（matching）是一組邊的集合，其中任意兩條邊都沒有公共頂點。
最大匹配：一個圖所有匹配中，所含匹配邊數最多的匹配，稱為這個圖的最大匹配。
最大權匹配：在一個帶邊權的二分圖的所有匹配中，邊權和最大的匹配，稱為這個圖的最大權匹配。
完美匹配：如果一個二分圖的某個匹配中，所有的頂點都是匹配點，那么它就是一個完美匹配。
最佳匹配：二分圖 G 的每條邊都有權值，則權值和最大的完美匹配稱為最佳匹配。
可行頂標：給二分圖每個節點 i 分配一個權值 l(i) ，對于所有邊(u, v) 滿足 w(u, v) <= l(u) + l(v) 的點權集合。如圖所示，集合 { a: 30, b: 0, c: 40, d: 20, e: 90, f: 0 } 就是該二分圖的一組可行頂標。一個二分圖有無數個可行頂標。
相等子圖：對于某一組可行頂標，我們吧包含所有點但只包含滿足 w(u, v) = l(u) + l(v) 的邊的子圖，稱為該可行頂標下的生成子圖。
匈牙利算法（感興趣可以自行百度學習）：該算法用于求解二分圖的最大匹配算法，核心策略如下：
- 如果能匹配，直接匹配
- 如果不能匹配，找一條增廣路，對增廣路（增廣路定義：一條 非匹配邊->匹配邊->非匹配邊->......->非匹配邊 的路徑。有的博客也叫交錯路）的邊取補邊，來增加一條匹配邊
km 依賴定理及證明
定理：
如果二分圖存在某組可行頂標，并且該可行頂標的相等子圖存在完美匹配，那么該匹配就是原二分圖的最佳匹配。
證明：
考慮原二分圖的任意一組完美匹配 M ，其邊權和 val(M)等于每條匹配邊（匹配邊沒有公共頂點）的權值和，又根據可行頂標的定義，我們可以得出任意一組完美匹配的邊權和都小于等于任意一組可行頂標的點權和。
如果存在一組可行頂標且該可行頂標的相等子圖存在完美匹配，那么該相等子圖的完美匹配 M'的邊權和 val(M')如下。（因為相等子圖只存在 w(u, v) = l(u) + l(v) 的邊）
顯然對于任意的完美匹配 M，val(M) <= val(M')，所以 M'就是權值和最大的完美匹配，即最佳匹配。
執行步驟
因為二分圖兩邊點的個數相等，假設個數為 n。
首先我們要初始化二分圖的可行頂標，二分圖左邊的點可行頂標取值為：以這個點為端點的最大邊權值，二分圖右邊的點可行頂標取值為：0
我們依次為左邊的點匹配，匹配準則是：可行頂標的和等于邊權值。（滿足相等子圖）
對于左邊節點 u 的匹配規則是：如果能匹配那么直接匹配，如果不能匹配就以 u 為起點，找交錯路，這些交錯路會組成一棵以節點 u 為根節點的交錯樹，樹中的任意兩條邊都是滿足匹配準則。如果存在一個葉子節點 v 與其父節點滿足匹配準則，并且是非匹配邊（存在增廣路），那么進行增廣操作（對增廣路中的匹配邊取補集），來增加一條匹配邊。如果沒有葉子節點滿足匹配準則（葉子節點都是匹配點），那么就調整可行頂標的值，如何調整呢？
我們把二分圖左邊在交錯樹中的點集記為 S，右邊在交錯樹中的點集記為 T，左邊不在交錯樹中的點集記為 S'，右邊不在交錯樹的點集記為 T'
- 集合 S 中的點，可行頂標減少 slack_min
- 集合 T 中的點，可行頂標增加 slack_min
根據左右頂點所在集合，我們可以把二分圖中的邊分成 4 種：
- 左頂點在 S 中，右頂點在 T 中，可行頂部和不變，滿足相等子圖
- 左頂點在 S 中，右頂點在 T'中，可行頂標和變小，有可能加入相等子圖，但是我們需要需要滿足可行頂部的定義：可行頂部的和大于等于邊權和，所以我們需要讓slack_min 取值為 min(l(u) + l(v) - w(u, v)) , (u 為 S'中的點，v 為集合 T'中的點）
- 左頂點在 S'中，右頂點在 T 中，可行頂部和變大，不可能加入相等子圖
- 左頂點在 S'中，右頂點在 T'中，保持不變
當一個新點 u 加入集合 T 有兩種情況：
- 是未匹配點，則找到增廣路
- 和 S'中的點已經匹配，繼續增廣，找 u'
這樣每調整一輪可行頂標，集合 T 至少增加一個點，那么至多修改 n 次頂標后，就可以找到增廣路。
代碼運行過程演示
完美婚姻問題為例：現在有 3 男 3 女，不同的男生和不同的女生之間有不同的好感值，情況如圖所示（如果沒有連邊，代表好感度為 0），我們希望讓他們兩兩配對，使得整體的好感度最大。
初始化策略：構造一個可行頂標，滿足 w(u, v) <= l(u) + l(v)，構造方案：所有男生可行頂標取值：0，所有女生取值：最大好感值
逐一為每個女生找對象，只有滿足可行頂和等于邊權才能配對
女一：
- 第一輪
- 女一與男一：10 + 0 = 10，配對成功
女二：
- 第一輪：
- 女二和男一：40 + 0 != 20，配對失敗
- 女二和男二：40 + 0 = 40，配對成功
女三：
第一輪：
- 女三和男二：110 + 0 = 110，但是男二與女二配對了，讓女二調整，發現除了男二沒有符合配對條件的，所以女三和男二配對失敗，失敗原因是，男二與女二配對了且女二不能調整。
- 女三和男三：110 + 0 != 30，配對失敗
- 第一輪配對失敗了，訪問過的女生為女二、女三，訪問過的男生為男二，男一，男三，男一至少需要調整 20 才能與女二配對成功，男三至少還需要調整 80 才能配對成功。所以 slack_min 等于 20。調整可行頂標，女二、女三減少 20，男三增加 30，如下圖所示：
第二輪：
- 女三和男二：90 + 20 = 110， 但是男二和女二配對了，讓女二嘗試換對象，發現男一符合條件，但是男一已經和女一配對，嘗試女一換對象，發現男三符合調整，所以此時女一換成了男三，女二換成男一，女三與男二配對，如圖所示：
遞歸版本的代碼：
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int MAXN = 305;
const int INF = 0x3f3f3f3f;
int love[MAXN][MAXN]; // 記錄每個妹子和每個男生的好感度
int ex_girl[MAXN]; // 每個妹子的期望值
int ex_boy[MAXN]; // 每個男生的期望值
bool vis_girl[MAXN]; // 記錄每一輪匹配匹配過的女生
bool vis_boy[MAXN]; // 記錄每一輪匹配匹配過的男生
int match[MAXN]; // 記錄每個男生匹配到的妹子 如果沒有則為-1
int slack[MAXN]; // 記錄每個漢子如果能被妹子傾心最少還需要多少期望值
int N;
bool dfs(int girl)
{
vis_girl[girl] = true;
for (int boy = 0; boy < N; ++boy) {
if (vis_boy[boy]) continue; // 每一輪匹配 每個男生只嘗試一次
int gap = ex_girl[girl] + ex_boy[boy] - love[girl][boy];
if (gap == 0) { // 如果符合要求
vis_boy[boy] = true;
if (match[boy] == -1 || dfs( match[boy] )) { // 找到一個沒有匹配的男生 或者該男生的妹子可以找到其他人
match[boy] = girl;
return true;
}
} else {
slack[boy] = min(slack[boy], gap); // slack 可以理解為該男生要得到女生的傾心 還需多少期望值 取最小值 備胎的樣子【捂臉
}
}
return false;
}
int KM()
{
memset(match, -1, sizeof match); // 初始每個男生都沒有匹配的女生
memset(ex_boy, 0, sizeof ex_boy); // 初始每個男生的期望值為0
// 每個女生的初始期望值是與她相連的男生最大的好感度
for (int i = 0; i < N; ++i) {
ex_girl[i] = love[i][0];
for (int j = 1; j < N; ++j) {
ex_girl[i] = max(ex_girl[i], love[i][j]);
}
}
// 嘗試為每一個女生解決歸宿問題
for (int i = 0; i < N; ++i) {
fill(slack, slack + N, INF); // 因為要取最小值 初始化為無窮大
while (1) {
// 為每個女生解決歸宿問題的方法是 ：如果找不到就降低期望值，直到找到為止
// 記錄每輪匹配中男生女生是否被嘗試匹配過
memset(vis_girl, false, sizeof vis_girl);
memset(vis_boy, false, sizeof vis_boy);
if (dfs(i)) break; // 找到歸宿 退出
// 如果不能找到 就降低期望值
// 最小可降低的期望值
int d = INF;
for (int j = 0; j < N; ++j)
if (!vis_boy[j]) d = min(d, slack[j]);
for (int j = 0; j < N; ++j) {
// 所有訪問過的女生降低期望值
if (vis_girl[j]) ex_girl[j] -= d;
// 所有訪問過的男生增加期望值
if (vis_boy[j]) ex_boy[j] += d;
// 沒有訪問過的boy 因為girl們的期望值降低，距離得到女生傾心又進了一步！
else slack[j] -= d;
}
}
}
// 匹配完成 求出所有配對的好感度的和
int res = 0;
for (int i = 0; i < N; ++i)
res += love[ match[i] ][i];
return res;
}
int main()
{
while (~scanf("%d", &N)) {
for (int i = 0; i < N; ++i)
for (int j = 0; j < N; ++j)
scanf("%d", &love[i][j]);
printf("%d\n", KM());
}
return 0;
}
參考文檔：
- https://oi-wiki.org/graph/graph-matching/bigraph-weight-match/
- https://www.cnblogs.com/wenruo/p/5264235.html?
