作者 ｜ 劉潔 

問(wèn)題概述

一筆訂單最多可使用所含電影票數(shù)目張兌換券。換而言之，用戶(hù)選了幾個(gè)座位，最多便能使用幾張兌換券，兌換券有三個(gè)屬性，分別是：

面值（元）：在不支持補(bǔ)差的情況下，票價(jià)小于等于面值才可以使用

固定支付金額（元）：滿足兌換券的使用條件下，需要支付的錢(qián)。

補(bǔ)差（是 / 否）：如果支持補(bǔ)差，當(dāng)票價(jià)大于面值時(shí)，還需要額外支付 （票價(jià) - 面值）元

• 舉個(gè)栗子：小明有一張面值 50，固定支付 19 元且支持補(bǔ)差的兌換券。那么他能使用這張兌換券去購(gòu)買(mǎi)票價(jià)小于等于 50 元的電影票，只需支付 19 元。因?yàn)橹С盅a(bǔ)差，所以他能購(gòu)買(mǎi)票價(jià)為 60 元（大于面值）的電影票，需支付（19 + （ 60 - 50））既 29 元。

我們問(wèn)題是：用戶(hù)下了一筆訂單，訂單中有 x（根據(jù)業(yè)務(wù)場(chǎng)景，x <= 6）張電影票，y 張兌換券，從這 y 張兌換券中選擇不超過(guò) x 張兌換券，使得該筆訂單的實(shí)際支付金額最少，如果有多種解決方案，那么根據(jù)以下優(yōu)先級(jí)為用戶(hù)推薦選券的方案：

優(yōu)先級(jí) 1: 選擇實(shí)際支付金額少的方案

優(yōu)先級(jí) 2: 如果實(shí)際支付金額一致，則優(yōu)先使用面值小的方案

• 原因：如果用戶(hù)想購(gòu)買(mǎi)一張票價(jià)為 38 元的電影票，當(dāng)前他有一張 40 元和一張 60 元的兌換券，任意使用一張兌換券能得到的實(shí)際支付金額都是 0 元，那么優(yōu)先為用戶(hù)選擇 40 元的兌換券，這樣 60 元的兌換券就能服務(wù)于用戶(hù)的下一筆訂單，更能為用戶(hù)省錢(qián)。

• 優(yōu)先級(jí) 3: 若面值大小也一致，則優(yōu)先使用優(yōu)惠券所在券包消耗券數(shù)目多的優(yōu)惠券
• 優(yōu)先級(jí) 4: 若消耗券數(shù)目一致，則優(yōu)先使用過(guò)期時(shí)間早的優(yōu)惠券

技術(shù)方案

方案一：貪心

具體步驟：排序

對(duì)票價(jià)從大到小排序，讓票價(jià)高的電影票優(yōu)先選擇，目的就是為了金額大的電影票優(yōu)先使用限制條件少（既面值大）的兌換券，讓券面值得到充分利用，每個(gè)票和券的組合都盡可能是最優(yōu)解。

證明方法：舉反例法

很不幸，很快就找出一個(gè)反例推翻了這個(gè)方案，反例如圖所示

方案二：暴力枚舉

枚舉所有方案，從這所有方案中求出最優(yōu)解，但是時(shí)間復(fù)雜度高達(dá) C(y, x) * A(x, x) 也就是 O(n!)，若按照 1s 鐘計(jì)算機(jī)能運(yùn)行 10^8 次計(jì)算這樣的標(biāo)準(zhǔn)，當(dāng) n = 13 的時(shí)候，需要超過(guò) 10s 才能得到答案，并且 n 每增加 1，時(shí)間就會(huì)擴(kuò)大 n 倍。

解決方案三：二分圖最優(yōu)匹配算法——KM 算法

km（Kuhn-Munkres）算法簡(jiǎn)介

km 算法是一種二分圖最佳匹配算法，該算法主要用于解決一個(gè)經(jīng)典的問(wèn)題模型：完美婚姻問(wèn)題。該問(wèn)題的描述如下：n 個(gè)男生和 n 個(gè)女生相親，第 i 個(gè)男生和第 j 個(gè)女生在一起的幸福值是 val(i, j)，如何讓 n 個(gè)男生和 n 個(gè)女生完成一一配對(duì)，使得這個(gè)整體的總幸福值最大。我們的問(wèn)題和完美婚姻問(wèn)題模型有點(diǎn)相似，并且經(jīng)過(guò)調(diào)研 km 算法時(shí)間復(fù)雜度是 n^3，km 算法有一個(gè)非常大的優(yōu)點(diǎn)就是，他可以求出哪張券用于哪張電影票，適用于選座相關(guān)的業(yè)務(wù)場(chǎng)景。

km 算法落地（對(duì) km 算法不熟悉的同學(xué)可以先瀏覽第三部分）

我們把兌換券看成男生，電影票看成女生，用兌換券 j 購(gòu)買(mǎi)電影票 i 的花費(fèi)是 -w(i, j)去建圖，如果兌換券 j 無(wú)法購(gòu)買(mǎi)電影票 i，那么花費(fèi) w(i, j)設(shè)置為負(fù)無(wú)窮大，去構(gòu)造一個(gè)二分圖嘗試求解，我們會(huì)遇到一些問(wèn)題：

改造一：如何滿足 km 算法的使用條件？

因?yàn)?km 算法是用于求解二分圖的最佳匹配，也就是說(shuō)二分圖必須存在最佳匹配才能使用 km 算法求解。存在最佳匹配的必要條件是：必須兩邊的點(diǎn)相同，而且至少存在一種匹配方案使得所有的點(diǎn)都被匹配。所以我們需要補(bǔ)點(diǎn)和補(bǔ)邊（補(bǔ)點(diǎn)和補(bǔ)邊也是使用 km 算法的常見(jiàn)的技巧）。補(bǔ)邊策略：將不存在的邊，權(quán)重設(shè)為-inf。補(bǔ)點(diǎn)策略：新增 x 張兌換券，第 y + i 張兌換券跟第 i 張電影票連邊，權(quán)值為電影票的原價(jià)，這樣一來(lái)可以保障把無(wú)窮大的結(jié)果排除在外，二來(lái)不需要再額外再計(jì)算使用原價(jià)購(gòu)買(mǎi)的情況。

改造二：如何在多個(gè)解中求出滿足優(yōu)先級(jí)的解？

我們可以把所有兌換券按照面值由小到大排序，如果面值一致，那么按照入賬時(shí)間從早到晚排序，如果入駐時(shí)間一致，按照過(guò)期時(shí)間由早到晚排序，簡(jiǎn)而言之，把優(yōu)先級(jí)高的券放在前面。枚舉數(shù)量 k，對(duì)前 k 個(gè)兌換券和所有的電影票加入 km 模型中，計(jì)算出最少花費(fèi)，只有花費(fèi)變得比之前更小才更新答案。這樣可以保證取得最少花費(fèi)的同時(shí)，還能滿足優(yōu)先級(jí)。還有一個(gè)好處是，如果后續(xù) pm 對(duì)策略的優(yōu)先級(jí)進(jìn)行調(diào)整，那么我們可以更改最初的排序規(guī)則即可。但是時(shí)間復(fù)雜度此時(shí)變成了 n^4。

如圖所示，當(dāng) k 等于 2 的時(shí)候取得最優(yōu)解，k=3 的時(shí)候有可能匹配到優(yōu)先級(jí)低的券。

改造三、時(shí)間復(fù)雜度的優(yōu)化

經(jīng)過(guò)改造一和改造二的處理后，算法時(shí)間復(fù)雜度是：（x+y)^4 + y*logy（x 代表電影票張數(shù)，y 代表兌換券張數(shù)）

時(shí)間復(fù)雜度分析：經(jīng)過(guò)補(bǔ)點(diǎn)操作后，二分圖兩邊的點(diǎn)都是 x + y 個(gè)。因?yàn)?km 算法的時(shí)間復(fù)雜度是 n ^ 3 次方，n 為二分圖單側(cè)的點(diǎn)的個(gè)數(shù)。所以當(dāng)前的時(shí)間復(fù)雜度是 （x+y)^3 。為了處理匹配的優(yōu)先級(jí)問(wèn)題，我們對(duì)優(yōu)惠券進(jìn)行了優(yōu)先級(jí)排序，時(shí)間復(fù)雜度是y*logy，在運(yùn)行 km 算法的時(shí)候，枚舉了數(shù)量 k，所以總時(shí)間復(fù)雜度為（x+y)^4 + y*logy。

改造方法

具體步驟：對(duì)于每一張電影票，預(yù)處理出對(duì)于這張電影票優(yōu)先級(jí)最高的 n（n 為當(dāng)前的電影票張數(shù)）張，把這些兌換券去重，我們就能得到最多 nn 張兌換券。用著 nn 張兌換券代替原來(lái)的所有優(yōu)惠券

• 時(shí)間復(fù)雜度（優(yōu)化后，算法的時(shí)間復(fù)雜度跟優(yōu)惠券數(shù)目無(wú)關(guān)，而跟電影票張數(shù)有關(guān)，目前的業(yè)務(wù)場(chǎng)景是，電影票最多不超過(guò) 4 張，所以該算法有較好的性能）：

• 預(yù)處理出x*x?張優(yōu)惠券的時(shí)間復(fù)雜度：x^2 * y * logx(x 為電影票數(shù)目，y 為優(yōu)惠券數(shù)目）
• 運(yùn)行 km 算法求最優(yōu)解的時(shí)間復(fù)雜度：((1 + x) * x)^4 + 2 * x^2 *logx(x 為電影票數(shù)目)
• 總時(shí)間復(fù)雜度：x^2 * y * logx? + ((1 + x) * x)^4 + 2 * x^2 *logx(x 為電影票數(shù)目，且 0 < x <= 4)

收益：

當(dāng)用戶(hù)有 500 張兌換券（極限值時(shí)），能非常迅速的計(jì)算出最優(yōu)策略，幾乎無(wú)延遲。

km 原理證明

前置知識(shí)

二分圖：又稱(chēng)作二部圖，是圖論中的一種特殊模型。設(shè) G=(V,E)是一個(gè)無(wú)向圖，如果頂點(diǎn) V 可分割為兩個(gè)互不相交的子集(A,B)，并且圖中的每條邊（i，j）所關(guān)聯(lián)的兩個(gè)頂點(diǎn) i 和 j 分別屬于這兩個(gè)不同的頂點(diǎn)集(i in A,j in B)，則稱(chēng)圖 G 為一個(gè)二分圖。

匹配：在二分圖中，一個(gè)「匹配」（matching）是一組邊的集合，其中任意兩條邊都沒(méi)有公共頂點(diǎn)。

最大匹配：一個(gè)圖所有匹配中，所含匹配邊數(shù)最多的匹配，稱(chēng)為這個(gè)圖的最大匹配。

最大權(quán)匹配：在一個(gè)帶邊權(quán)的二分圖的所有匹配中，邊權(quán)和最大的匹配，稱(chēng)為這個(gè)圖的最大權(quán)匹配。

完美匹配：如果一個(gè)二分圖的某個(gè)匹配中，所有的頂點(diǎn)都是匹配點(diǎn)，那么它就是一個(gè)完美匹配。

最佳匹配：二分圖 G 的每條邊都有權(quán)值，則權(quán)值和最大的完美匹配稱(chēng)為最佳匹配。

可行頂標(biāo)：給二分圖每個(gè)節(jié)點(diǎn) i 分配一個(gè)權(quán)值 l(i) ，對(duì)于所有邊(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)。一個(gè)二分圖有無(wú)數(shù)個(gè)可行頂標(biāo)。

相等子圖：對(duì)于某一組可行頂標(biāo)，我們吧包含所有點(diǎn)但只包含滿足 w(u, v) = l(u) + l(v) 的邊的子圖，稱(chēng)為該可行頂標(biāo)下的生成子圖。

匈牙利算法（感興趣可以自行百度學(xué)習(xí)）：該算法用于求解二分圖的最大匹配算法，核心策略如下：

• 如果能匹配，直接匹配
• 如果不能匹配，找一條增廣路，對(duì)增廣路（增廣路定義：一條 非匹配邊->匹配邊->非匹配邊->......->非匹配邊 的路徑。有的博客也叫交錯(cuò)路）的邊取補(bǔ)邊，來(lái)增加一條匹配邊

km 依賴(lài)定理及證明

定理：

如果二分圖存在某組可行頂標(biāo)，并且該可行頂標(biāo)的相等子圖存在完美匹配，那么該匹配就是原二分圖的最佳匹配。

證明：

考慮原二分圖的任意一組完美匹配 M ，其邊權(quán)和 val(M)等于每條匹配邊（匹配邊沒(méi)有公共頂點(diǎn)）的權(quán)值和，又根據(jù)可行頂標(biāo)的定義，我們可以得出任意一組完美匹配的邊權(quán)和都小于等于任意一組可行頂標(biāo)的點(diǎn)權(quán)和。

如果存在一組可行頂標(biāo)且該可行頂標(biāo)的相等子圖存在完美匹配，那么該相等子圖的完美匹配 M'的邊權(quán)和 val(M')如下。（因?yàn)橄嗟茸訄D只存在 w(u, v) = l(u) + l(v) 的邊）

顯然對(duì)于任意的完美匹配 M，val(M) <= val(M')，所以 M'就是權(quán)值和最大的完美匹配，即最佳匹配。

執(zhí)行步驟

因?yàn)槎謭D兩邊點(diǎn)的個(gè)數(shù)相等，假設(shè)個(gè)數(shù)為 n。

首先我們要初始化二分圖的可行頂標(biāo)，二分圖左邊的點(diǎn)可行頂標(biāo)取值為：以這個(gè)點(diǎn)為端點(diǎn)的最大邊權(quán)值，二分圖右邊的點(diǎn)可行頂標(biāo)取值為：0

我們依次為左邊的點(diǎn)匹配，匹配準(zhǔn)則是：可行頂標(biāo)的和等于邊權(quán)值。（滿足相等子圖）

對(duì)于左邊節(jié)點(diǎn) u 的匹配規(guī)則是：如果能匹配那么直接匹配，如果不能匹配就以 u 為起點(diǎn)，找交錯(cuò)路，這些交錯(cuò)路會(huì)組成一棵以節(jié)點(diǎn) u 為根節(jié)點(diǎn)的交錯(cuò)樹(shù)，樹(shù)中的任意兩條邊都是滿足匹配準(zhǔn)則。如果存在一個(gè)葉子節(jié)點(diǎn) v 與其父節(jié)點(diǎn)滿足匹配準(zhǔn)則，并且是非匹配邊（存在增廣路），那么進(jìn)行增廣操作（對(duì)增廣路中的匹配邊取補(bǔ)集），來(lái)增加一條匹配邊。如果沒(méi)有葉子節(jié)點(diǎn)滿足匹配準(zhǔn)則（葉子節(jié)點(diǎn)都是匹配點(diǎn)），那么就調(diào)整可行頂標(biāo)的值，如何調(diào)整呢？

我們把二分圖左邊在交錯(cuò)樹(shù)中的點(diǎn)集記為 S，右邊在交錯(cuò)樹(shù)中的點(diǎn)集記為 T，左邊不在交錯(cuò)樹(shù)中的點(diǎn)集記為 S'，右邊不在交錯(cuò)樹(shù)的點(diǎn)集記為 T'

• 集合 S 中的點(diǎn)，可行頂標(biāo)減少 slack_min
• 集合 T 中的點(diǎn)，可行頂標(biāo)增加 slack_min

根據(jù)左右頂點(diǎn)所在集合，我們可以把二分圖中的邊分成 4 種：

1. 左頂點(diǎn)在 S 中，右頂點(diǎn)在 T 中，可行頂部和不變，滿足相等子圖
2. 左頂點(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)）
3. 左頂點(diǎn)在 S'中，右頂點(diǎn)在 T 中，可行頂部和變大，不可能加入相等子圖
4. 左頂點(diǎn)在 S'中，右頂點(diǎn)在 T'中，保持不變

當(dāng)一個(gè)新點(diǎn) u 加入集合 T 有兩種情況：

• 是未匹配點(diǎn)，則找到增廣路
• 和 S'中的點(diǎn)已經(jīng)匹配，繼續(xù)增廣，找 u'

這樣每調(diào)整一輪可行頂標(biāo)，集合 T 至少增加一個(gè)點(diǎn)，那么至多修改 n 次頂標(biāo)后，就可以找到增廣路。

代碼運(yùn)行過(guò)程演示

完美婚姻問(wèn)題為例：現(xiàn)在有 3 男 3 女，不同的男生和不同的女生之間有不同的好感值，情況如圖所示（如果沒(méi)有連邊，代表好感度為 0），我們希望讓他們兩兩配對(duì)，使得整體的好感度最大。

初始化策略：構(gòu)造一個(gè)可行頂標(biāo)，滿足 w(u, v) <= l(u) + l(v)，構(gòu)造方案：所有男生可行頂標(biāo)取值：0，所有女生取值：最大好感值

逐一為每個(gè)女生找對(duì)象，只有滿足可行頂和等于邊權(quán)才能配對(duì)

女一：

• 第一輪
• 女一與男一：10 + 0 = 10，配對(duì)成功

女二：

• 第一輪：
• 女二和男一：40 + 0 != 20，配對(duì)失敗
• 女二和男二：40 + 0 = 40，配對(duì)成功

女三：

第一輪：

• 女三和男二：110 + 0 = 110，但是男二與女二配對(duì)了，讓女二調(diào)整，發(fā)現(xiàn)除了男二沒(méi)有符合配對(duì)條件的，所以女三和男二配對(duì)失敗，失敗原因是，男二與女二配對(duì)了且女二不能調(diào)整。
• 女三和男三：110 + 0 != 30，配對(duì)失敗
• 第一輪配對(duì)失敗了，訪問(wèn)過(guò)的女生為女二、女三，訪問(wèn)過(guò)的男生為男二，男一，男三，男一至少需要調(diào)整 20 才能與女二配對(duì)成功，男三至少還需要調(diào)整 80 才能配對(duì)成功。所以 slack_min 等于 20。調(diào)整可行頂標(biāo)，女二、女三減少 20，男三增加 30，如下圖所示：

第二輪：

• 女三和男二：90 + 20 = 110， 但是男二和女二配對(duì)了，讓女二嘗試換對(duì)象，發(fā)現(xiàn)男一符合條件，但是男一已經(jīng)和女一配對(duì)，嘗試女一換對(duì)象，發(fā)現(xiàn)男三符合調(diào)整，所以此時(shí)女一換成了男三，女二換成男一，女三與男二配對(duì)，如圖所示：

遞歸版本的代碼：

#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;
const int MAXN = 305;
const int INF = 0x3f3f3f3f;

int love[MAXN][MAXN];   // 記錄每個(gè)妹子和每個(gè)男生的好感度
int ex_girl[MAXN];      // 每個(gè)妹子的期望值
int ex_boy[MAXN];       // 每個(gè)男生的期望值
bool vis_girl[MAXN];    // 記錄每一輪匹配匹配過(guò)的女生
bool vis_boy[MAXN];     // 記錄每一輪匹配匹配過(guò)的男生
int match[MAXN];        // 記錄每個(gè)男生匹配到的妹子 如果沒(méi)有則為-1
int slack[MAXN];        // 記錄每個(gè)漢子如果能被妹子傾心最少還需要多少期望值

int N;


bool dfs(int girl)
{
    vis_girl[girl] = true;

    for (int boy = 0; boy < N; ++boy) {

        if (vis_boy[boy]) continue; // 每一輪匹配 每個(gè)男生只嘗試一次

        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] )) {    // 找到一個(gè)沒(méi)有匹配的男生 或者該男生的妹子可以找到其他人
                match[boy] = girl;
                return true;
            }
        } else {
            slack[boy] = min(slack[boy], gap);  // slack 可以理解為該男生要得到女生的傾心 還需多少期望值 取最小值 備胎的樣子【捂臉
        }
    }

    return false;
}

int KM()
{
    memset(match, -1, sizeof match);    // 初始每個(gè)男生都沒(méi)有匹配的女生
    memset(ex_boy, 0, sizeof ex_boy);   // 初始每個(gè)男生的期望值為0

    // 每個(gè)女生的初始期望值是與她相連的男生最大的好感度
    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]);
        }
    }

    // 嘗試為每一個(gè)女生解決歸宿問(wèn)題
    for (int i = 0; i < N; ++i) {

        fill(slack, slack + N, INF);    // 因?yàn)橐∽钚≈?初始化為無(wú)窮大

        while (1) {
            // 為每個(gè)女生解決歸宿問(wèn)題的方法是 ：如果找不到就降低期望值，直到找到為止

            // 記錄每輪匹配中男生女生是否被嘗試匹配過(guò)
            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) {
                // 所有訪問(wèn)過(guò)的女生降低期望值
                if (vis_girl[j]) ex_girl[j] -= d;

                // 所有訪問(wèn)過(guò)的男生增加期望值
                if (vis_boy[j]) ex_boy[j] += d;
                // 沒(méi)有訪問(wèn)過(guò)的boy 因?yàn)間irl們的期望值降低，距離得到女生傾心又進(jìn)了一步！
                else slack[j] -= d;
            }
        }
    }

    // 匹配完成 求出所有配對(duì)的好感度的和
    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?