作者|刘杰问题概述一个订单最多可以使用优惠券中包含的电影票数量。也就是说，用户可以选择几个座位，最多可以使用几张优惠券。优惠券具有三个属性，即：面值（元）：不支持票价时，票价小于或等于面值。使用固定支付金额（元）：满足兑换券使用条件时需要支付的金额。补差价（是/否）：若支持补差价，当票价大于面值时，需额外支付（票价-面值）元。例如：小明有面值50的兑换券，固定支付19元，支持补差价。那么他就可以用这张兑换券购买票价在50元以内的电影票，只需要支付19元。因为他支持补差价，他可以买到一张票价60元（大于面值）的电影票，需要支付（19+（60-50））也就是29元。我们的问题是：用户下单，订单中有x张（根据业务场景，x<=6）电影票和y张兑换券，从y张兑换券中选出不超过x张兑换券,这样这个订单的实际支付金额是最少的。如果有多个方案，则按照以下优先级为用户推荐优惠券选择方案：优先级1：选择实际支付金额最小的方案。优先级2：如果实际支付金额相同，优先使用面值小的方案原因：如果用户想购买票价38元的电影票，他目前有40元以及一张60元兑换券，而使用任意一张兑换券所能获得的实际支付金额为0元，所以优先为用户选择一张40元兑换券，这样60元兑换券才能生效用户的下一个订单并为用户省钱。优先级三：如果面值相同，则使用优惠券包中消费券数量最多的优惠券。优先级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)设为负infinity，构造一个二部图来尝试求解，我们会遇到一些问题：变换1：如何满足km算法的使用条件？因为km算法是求解二部图的最佳匹配，也就是说二部图必须有最佳匹配才能被km算法求解。最佳匹配存在的必要条件是：两边的点必须相同，并且至少存在一种匹配方案，使得所有的点都匹配。所以我们需要填充点和边（填充点和边也是使用km算法的常用技术）。边填充策略：设置不存在边的权重为-inf。补货策略：添加x张兑换券，y+i张兑换券与第i张电影票相连，权重为电影票原价，这样可以排除无限结果。需要计算使用原价加购的情况。变换2：如何在多个解中找到满足优先级的解？我们可以把所有兑换券按照面值从小到大排序。如果面值相同，则按照入场时间从早到晚排序。如果结算时间相同，按照到期时间从早到晚排序。简而言之，优先将较高的优惠券放在前面。枚举数字k，将前k张代金券和所有电影票加入到km模型中，计算最小成本，只有当成本变得比之前更小时才更新答案。这确保在满足优先级的同时获得最少的成本。还有一个好处是，如果后续的pm调整了policy的优先级，那么我们就可以改变最初的排序规则。但是此时时间复杂度变成了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为当前电影票的张数），去掉这些兑换券，最多可以得到n张兑换券。使用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
