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