双约束下的行权 premium 配置(delta 与 vega 双预算)
Two-Budget Strike-Premium Knapsack (Delta and Vega Caps)
开始编码某波动率桌台有 N 只候选期权合约的菜单,每只已由离线 sensitivity 引擎预先分桶为整数化的希腊值消耗:占用 delta_use[i] 单位的 delta 预算与 vega_use[i] 单位的 vega 预算;同时每只携带带符号整数 premium[i](正数为收到的 premium,负数为对冲成本)。桌台希望挑出一个候选子集,使总 delta 消耗不超过 delta_budget 且总 vega 消耗不超过 vega_budget,最大化总 premium。实现 solution(delta_use: list[int], vega_use: list[int], premium: list[int], delta_budget: int, vega_budget: int) -> int,返回可达到的最大总 premium。空集恒可行(premium 0),故答案非负。
举例,solution([1,2,3], [2,1,3], [10,8,15], 4, 4) 返回 18:取候选 0 与 1(delta 1+2=3 ≤ 4,vega 2+1=3 ≤ 4,premium 10+8 = 18);单取候选 2 得 15,但再加任何一只都会击穿至少一个预算。对冲示例,solution([2,1,3], [1,2,2], [5,-3,8], 4, 3) 返回 8:单取候选 2(delta 3 ≤ 4,vega 2 ≤ 3,premium 8)优于把负 premium 的候选 1 与候选 0 一起取(5 + (-3) = 2)。空集恒可选,故 premium 全为非正的菜单返回 0。
两个对抗子情形请先想清楚:所有 premium[i] <= 0 时答案为 0,因空集胜过任何包含;某只候选 delta_use[i] > delta_budget 或 vega_use[i] > vega_budget 时永不可被选取但不报错——静默丢弃。
实现细节由 stubs/stub.py 提供。
实践背景
多希腊风险预算下的行权配置是期权桌台日常的核心场景:sensitivity 引擎给出每只合约的 delta 与 vega 消耗(已按桌台风险政策分桶为整数单位),中后台对当节施加硬性 delta 与 vega 上限,模型给出每只的 premium 估计。部分"候选"是上游 pipeline 注入的负 premium 对冲腿,由优化器自行决定是否打包变现。双预算版本比单预算组合背包难得多——按比值排序(premium / delta 或 premium / vega)的贪心已不能取到最优,因为 delta 上便宜的候选可能 vega 上昂贵、反之亦然,二资源前沿是真正的二维。二维 DP 以"预算维度的平方"为代价精确刻画离散权衡;当合约数或预算粒度变大时,生产环境会切到商用 MIP,但本题的"分桶整数"正是教科书 DP 的标准用武之地。
约束条件
- 0 <= N <= 80,其中 `N == len(delta_use) == len(vega_use) == len(premium)`
- 0 <= `delta_use[i]` <= 50(整数;单只 delta 消耗)
- 0 <= `vega_use[i]` <= 50(整数;单只 vega 消耗)
- -1000 <= `premium[i]` <= 1000(带符号整数;可为负,对应对冲腿)
- 0 <= `delta_budget` <= 200(整数;delta 总上限)
- 0 <= `vega_budget` <= 200(整数;vega 总上限)
- 若某只候选 `delta_use[i] > delta_budget` 或 `vega_use[i] > vega_budget`,静默跳过(不报错)
- 空输入(`N == 0`)返回 `0`;若所有 premium 非正,则空集为最优,答案为 `0`
- 返回 Python `int`;因空集恒可行,答案恒 >= 0
样例
Case 1 · statement-example: pick 0+1 over 2
输入: [[1,2,3],[2,1,3],[10,8,15],4,4]
期望: 18
取候选 0 与 1:delta 1+2=3, vega 2+1=3, premium 10+8=18,胜过单取候选 2 的 15.
Case 2 · statement-example: hedge dominated by lone winner
输入: [[2,1,3],[1,2,2],[5,-3,8],4,3]
期望: 8
单取候选 2 得 8,优于含负 premium 的对冲组合.
Case 3 · typical: small four-candidate basic
输入: [[1,2,3,4],[2,2,1,3],[3,5,4,7],5,5]
期望: 10
Case 4 · typical: cap binds delta side
输入: [[3,2,4,1],[1,2,1,2],[6,4,9,2],6,5]
期望: 13
Case 5 · typical: cap binds vega side
输入: [[1,2,1,3],[4,3,2,5],[8,6,4,9],4,6]
期望: 12
Case 6 · boundary: empty inputs
输入: [[],[],[],10,10]
期望: 0
N=0 返回 0.
Case 7 · boundary: both budgets zero with free items
输入: [[0,0,1],[0,0,1],[5,3,7],0,0]
期望: 8
两预算均为 0,仅 0 成本候选可取:5+3=8.
Case 8 · boundary: single candidate fits
输入: [[3],[2],[7],3,2]
期望: 7
Case 9 · adversarial: all premiums negative
输入: [[1,2,3],[2,1,2],[-5,-3,-1],10,10]
期望: 0
全部 premium 为负,空集胜出,0.
Case 10 · adversarial: only one candidate fits at all
输入: [[5,6,1],[6,5,1],[100,50,2],4,4]
期望: 2
只有第三只能装下;premium=2.
最近提交
还没有提交记录。
编码区
实现 solution(...)。本地运行当前支持 Python 可见样例;服务端提交会运行可见样例和隐藏测试。
默认展示公开样例。点击「运行样例」后会在这里显示实际输出;点击「提交评测」会进入隐藏测试。
Case 1 · statement-example: pick 0+1 over 2
输入: [[1,2,3],[2,1,3],[10,8,15],4,4]
期望: 18
取候选 0 与 1:delta 1+2=3, vega 2+1=3, premium 10+8=18,胜过单取候选 2 的 15.
Case 2 · statement-example: hedge dominated by lone winner
输入: [[2,1,3],[1,2,2],[5,-3,8],4,3]
期望: 8
单取候选 2 得 8,优于含负 premium 的对冲组合.
Case 3 · typical: small four-candidate basic
输入: [[1,2,3,4],[2,2,1,3],[3,5,4,7],5,5]
期望: 10
Case 4 · typical: cap binds delta side
输入: [[3,2,4,1],[1,2,1,2],[6,4,9,2],6,5]
期望: 13
Case 5 · typical: cap binds vega side
输入: [[1,2,1,3],[4,3,2,5],[8,6,4,9],4,6]
期望: 12
Case 6 · boundary: empty inputs
输入: [[],[],[],10,10]
期望: 0
N=0 返回 0.
Case 7 · boundary: both budgets zero with free items
输入: [[0,0,1],[0,0,1],[5,3,7],0,0]
期望: 8
两预算均为 0,仅 0 成本候选可取:5+3=8.
Case 8 · boundary: single candidate fits
输入: [[3],[2],[7],3,2]
期望: 7
Case 9 · adversarial: all premiums negative
输入: [[1,2,3],[2,1,2],[-5,-3,-1],10,10]
期望: 0
全部 premium 为负,空集胜出,0.
Case 10 · adversarial: only one candidate fits at all
输入: [[5,6,1],[6,5,1],[100,50,2],4,4]
期望: 2
只有第三只能装下;premium=2.