拆单两腿对冲:最小化基差错配
Partition Orders to Minimize Basis Mismatch
开始编码某做基差套利的台子拿到一批待执行的同标的 lot 清单 lots(每个元素是该笔订单的整数股数)。策略要把这批单子两腿同步执行——一腿去 A 场所、另一腿去 B 场所,希望两腿成交量尽可能接近,这样残差敞口(basis mismatch)就最小、被持仓 overnight 的尾部风险也最小。请算出在「每个 lot 必须整体落到 A 或 B 之一、不能拆单」的约束下,可达到的最小 |sum(A) − sum(B)|。
请实现 solution(lots: list[int]) -> int,返回最优分组下两腿成交量之差的绝对值。注意:(a)允许某一组为空;(b)lots 可以为空,此时返回 0;(c)lot 是非负整数,可以为 0;(d)只关心两组总和之差,不需要返回具体的分组方案。参考实现位于 stubs/stub.py。
示例:solution([3, 1, 4, 2, 2]) 应返回 0。总量 12,把 {4, 2} 放 A、{3, 1, 2} 放 B,两腿都是 6,basis mismatch 为 0,完美对冲。再看 solution([1, 6, 11, 5]):总量 23 是奇数,最完美的拆法都必然留下至少 1 的奇偶残差;事实上 {11} 对 {1, 5, 6} = 12 给出差 1,已是最优——奇偶下界达到。反例提示:贪心地「每次把最大的 lot 丢给当前更小那组」对 [8, 7, 6, 5, 4] 会依次得到 A={8}、B={7}、B={7,6}=13、A={8,5}=13、然后 4 任放一边,最终差 4;而真正最优是 A={8,7}=15 对 B={6,5,4}=15,差 0。差距 4 在小例子里看着不大,但在真实清单上就是几十万的隔夜敞口——所以不能贪心。
枚举每个 lot 的 A/B 归属是 2^n 种组合,n=200 就完全不可行。关键观察是我们其实只关心 A 组的总和而不是它的具体内容——所以状态可以从「具体子集」压成「子集和」,只有 total + 1 种可能值。这把搜索空间从指数压到 O(n · total),是「子集和 / 0-1 背包」家族的标准武器。在真实做市与基差套利里,这套 DP 还有更细的变体(带容量上限的 split、按风险敞口而非股数 split、加上手续费阶梯),但先把这个最干净的版本写对——后续所有变体都从这里长出来。
约束条件
- 0 ≤ len(lots) ≤ 200
- 0 ≤ lots[i] ≤ 1000
- sum(lots) ≤ 50000
- 返回值是非负整数
- 允许某一组为空(即把全部 lot 放进另一组)
样例
Case 1 · five lots, perfect split exists
输入: [[3,1,4,2,2]]
期望: 0
总量 12,恰好可以拆成 {4, 2} 与 {3, 1, 2},两边都是 6,差 0。基差完全对冲。
Case 2 · indivisible parity leaves a residue
输入: [[1,6,11,5]]
期望: 1
总量 23(奇数),最完美的二分必有奇偶残差。最优做法是 {11} 与 {1, 5, 6}=12,差为 1,无法再小。
最近提交
还没有提交记录。
编码区
实现 solution(...)。本地运行当前支持 Python 可见样例;服务端提交会运行可见样例和隐藏测试。
默认展示公开样例。点击「运行样例」后会在这里显示实际输出;点击「提交评测」会进入隐藏测试。
Case 1 · five lots, perfect split exists
输入: [[3,1,4,2,2]]
期望: 0
总量 12,恰好可以拆成 {4, 2} 与 {3, 1, 2},两边都是 6,差 0。基差完全对冲。
Case 2 · indivisible parity leaves a residue
输入: [[1,6,11,5]]
期望: 1
总量 23(奇数),最完美的二分必有奇偶残差。最优做法是 {11} 与 {1, 5, 6}=12,差为 1,无法再小。