← 返回编程题库
coding-two-budget-knapsack-strike-premium困难免费版2000ms未尝试

双约束下的行权 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_budgetvega_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 可见样例;服务端提交会运行可见样例和隐藏测试。

加载编辑器...
计时0:00

默认展示公开样例。点击「运行样例」后会在这里显示实际输出;点击「提交评测」会进入隐藏测试。

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.