从小奥到高等数学——小学奥数的圆寂之整数规划 最后更新于 2025-05-01 16:19:58

# 从小奥到高等数学——小学奥数的圆寂之整数规划 陈哲（首字母 cz，即初中）生 FlowerAccepted 看到了这样一道题： > 有 $n$ 个花朵要去郊游，现在有足够的 $a$ 座客车和 $b$ 座客车，一辆 $a$ 座客车租金 $x\kern1mm\tt{CCU}$（common coin 单位，为本文所有钱币的单位），一辆 $b$ 座客车租金 $y\kern1mm\tt{CCU}$，问怎样租用客车才能最省钱？ 其中 $n$，$x$，$y$，$a$，$b$ 是给定的常量。在下面例子中，$n = 240$，$x = 200$，$y = 300$, $a = 45$，$b = 60$，即 > 有 $240$ 个花朵要去郊游，现在有足够的 $45$ 座客车和 $60$ 座客车，一辆 $45$ 座客车租金 $200\kern1mm\tt{CCU}$，一辆 $60$ 座客车租金 $300\kern1mm\tt{CCU}$，问怎样租用客车才能最省钱？ ## Sol 1: 无脑暴力（$10\times \operatorname{rand}(0, 1)$ pts） 小学生小酥鱼会想到： 打表出奇迹！试呗！ 但要不重不漏，还是很难的！ 支持数据范围：$n \le 10$ ## Sol 2: 小学奥数贪心（$30$ pts） 可以看看哪种车性价比更高，优先租它直到座位数大于人数，然后一辆一辆减去这种车的数量，不够了就拿另一种车补。  $$ \footnotesize \text{图 S-AS01-01-1} \\ \text{示意图} $$ 选 $(1, 4)\kern1mm1100\kern1mm\tt{CCU}$ 即可。 支持数据范围：$n \le 10^8$。可以为全北京人规划出行！但不够！可以不重不漏，但数据大了呢？ ## Sol 3: 正解——整数规划（$100$ pts） 前置知识：~~修仙~~线性规划。 分支定界大法！抽象算法不太好描述，这里直接上样例。各位读者可以造一组数据照猫画画虎加深理解。 先设最优解 $X_1$ 辆 $45$ 座客车， $X_2$ 辆 $60$ 座客车，即 $$ LP_0 \\ \begin {alignedat}{4} &\min &z &= &200&X_1 + &300&X_2 \\ &s.t. &240 &\le &45&X_1 + &60&X_2 \\ &\kern1mm &0&\le&X_1 &, &X_2 \end {alignedat} $$ 解得 $z=1066\frac{2}{3}$，$X_1 = \frac{18}{3}$，$X_2=0$。 但这不是整数，不符合实际意义！ 那就分枝！ 强制将原来的线性规划拆成两个，看 $X_1$ 不为整数，就加一个条件使 $X_1$ 被分在它两侧的整数两侧， $$ LP_1 \\ \begin {alignedat}{4} &\min &z &= &200&X_1 + &300&X_2 \\ &s.t. &240 &\le &45&X_1 + &60&X_2 \\ &\kern1mm &6&\le&X_1 \\ &\kern1mm &0&\le&X_1 &, &X_2 \end {alignedat} \\ \kern1mm\\ LP_2 \\ \begin {alignedat}{4} &\min &z &= &200&X_1 + &300&X_2 \\ &s.t. &240 &\le &45&X_1 + &60&X_2 \\ &\kern1mm &5&\ge&X_1 \\ &\kern1mm &0&\le&X_1 &, &X_2 \end {alignedat} $$ $LP_1$ 无解，$LP_2$ 解得 $z = 1075$，$X_1 = 5$，$X_2 = \frac{1}{4}$，再对 $X_2$ 做类似的操作， $$ LP_{21} \\ \begin {alignedat}{4} &\min &z &= &200&X_1 + &300&X_2 \\ &s.t. &240 &\le &45&X_1 + &60&X_2 \\ &\kern1mm &5&\ge&X_1 \\ &\kern1mm &0&\ge&X_2 \\ &\kern1mm &0&\le&X_1 &, &X_2 \end {alignedat} \\ \kern1mm\\ LP_{22} \\ \begin {alignedat}{4} &\min &z &= &200&X_1 + &300&X_2 \\ &s.t. &240 &\le &45&X_1 + &60&X_2 \\ &\kern1mm &5&\ge&X_1 \\ &\kern1mm &1&\le&X_2 \\ &\kern1mm &0&\le&X_1 &, &X_2 \end {alignedat} $$ $LP_{21}$ 无解，$LP_{22}$ 解得 $z = 1100$，$X_1 = 4$，$X_2 = 1$。 好，我们得到正确答案啦！  $$ \footnotesize \text{图 AS01-01-2} \\ \text{示意图二号，惊现元首寄技} $$ 注意，自己练习时如果有多个有解的线性规划，则取结果最优的一个来分枝。 不算每次 $LP$ 复杂度 $O(\log n)$。支持数据范围：$n \le 10^{10}$。可以为全世界人规划 $\text{Hel tour}$！ 结束！