单笔上限下的多档行权配置（有界背包）
Multi-Strike Portfolio with Per-Strike Share Cap (Bounded Knapsack)
开始编码某多档行权期权配置桌台在整数现金预算 budget 与一组候选行权下作业；每只行权携带整数的单股成本 cost、带符号的单股期望回报 expected_return，以及显式的单笔股数上限 max_shares。实现 solution(budget: int, candidates: list[list]) -> float，返回所有满足 Σ k_i * cost_i ≤ budget 与 0 ≤ k_i ≤ max_shares_i 的整数股数选择下，总期望回报的最大值。组合经理可自由持有现金（现金回报为零），故返回值非负。candidates 为空与 budget == 0 均返回 0.0，结果类型为 Python float。
举例，solution(10, [[2, 3.0, 3], [3, 5.0, 2], [4, 4.5, 1]]) 返回 16.0：最优解是成本为三的行权买两股（成本六、回报十）加成本为二的行权买两股（成本四、回报六），合计成本十、回报 16.0；备选方案"三股成本二加一股成本四"仅得 13.5。再如 solution(7, [[2, -1.0, 5], [3, 4.0, 2]]) 返回 8.0——成本为二的候选单股期望回报为负，组合经理在该位上持有现金，只买入两股成本为三的候选。
两个对抗子情形需要先想清楚：当所有候选 expected_return ≤ 0 时，答案恒为 0.0（持有现金）；当所有候选 max_shares == 0 时，即使单股回报为正，答案仍为 0.0——零额度即零股。
实现细节由 stubs/stub.py 提供。
实践背景
多档行权的期权 overlay 与结构化产品桌台在现实中精确遇到这一问题：单 session 的固定现金预算、一份带桌台施加的单笔规模上限（集中度风险、gamma 上限、做市商库存）的行权菜单，以及波动率模型给出的单股期望回报估计。单笔上限让问题真正成为有界而非 0/1——与"每只名字只许一股"的合规型 overlay 不同，桌台确实希望同一档买多张合约，只是不能无上限。教科书递推——反向扫描的一维 DP 加单只多股内层展开、可选用二进制分解加速——是小 N 情形下的标准实现；当 N 或 max_shares 变大时，生产环境会切换到商用 MIP，但"离散有界"这一让问题变难的结构本身，正是该 DP 所捕获的。
约束条件
- 0 <= `budget` <= 4000
- 0 <= N <= 80，其中 `N = len(candidates)`
- 每个候选是长度为 3 的列表 `[cost, expected_return, max_shares]`
- 1 <= `cost` <= 4000（整数；整股成本，不允许碎股）
- -50.0 <= `expected_return` <= 50.0（带符号浮点数；单股期望回报）
- 0 <= `max_shares` <= 50（整数；单笔股数上限）
- `candidates` 为空返回 `0.0`；`budget == 0` 返回 `0.0`
- 若不存在任何能放进预算的正回报子集，返回 `0.0`（持有现金恒可行）
- 浮点比较容差：`rel_tol = 1e-9`, `abs_tol = 1e-12`
样例
Case 1 · statement-example: cost-3x2 + cost-2x2 = 16.0
输入: [10,[[2,3,3],[3,5,2],[4,4.5,1]]]
期望: 16
预算 10：成本 3 的行权买 2 股（回报 10）+ 成本 2 的行权买 2 股（回报 6）= 16.0；备选 3+1 股仅得 13.5。
Case 2 · statement-example: skip negative-return strike
输入: [7,[[2,-1,5],[3,4,2]]]
期望: 8
负回报候选不买；只买 2 股成本 3 的，回报 8.0。
Case 3 · typical: small two-strike basic
输入: [6,[[2,1.5,3],[3,2,2]]]
期望: 4.5
Case 4 · typical: cap binds vs budget
输入: [20,[[1,1,5],[2,3,4]]]
期望: 17
Case 5 · typical: ties on per-share return
输入: [10,[[2,2,3],[3,3,2],[5,5,1]]]
期望: 10
Case 6 · boundary: empty candidates
输入: [10,[]]
期望: 0
候选空，返回 0.0。
Case 7 · boundary: budget = 0
输入: [0,[[1,5,10]]]
期望: 0
预算为 0，无法买任何股，返回 0.0。
Case 8 · boundary: empty + budget zero
输入: [0,[]]
期望: 0
Case 9 · boundary: single candidate one share
输入: [5,[[5,3,1]]]
期望: 3
Case 10 · adversarial: all-negative expected returns
输入: [20,[[1,-1,5],[2,-0.5,3],[3,-2,4]]]
期望: 0
所有候选回报为负 -> 持有现金，0.0。
Case 11 · adversarial: every max_shares = 0
输入: [50,[[1,5,0],[2,4,0],[3,3,0]]]
期望: 0
每只候选额度为 0 -> 0.0。
Case 12 · adversarial: cost > budget for all
输入: [3,[[5,100,10],[10,50,5],[4,7,3]]]
期望: 0
所有候选成本都超过预算 -> 0.0。
最近提交
还没有提交记录。
编码区
实现 solution(...)。本地运行当前支持 Python 可见样例；服务端提交会运行可见样例和隐藏测试。
默认展示公开样例。点击「运行样例」后会在这里显示实际输出；点击「提交评测」会进入隐藏测试。
Case 1 · statement-example: cost-3x2 + cost-2x2 = 16.0
输入: [10,[[2,3,3],[3,5,2],[4,4.5,1]]]
期望: 16
预算 10：成本 3 的行权买 2 股（回报 10）+ 成本 2 的行权买 2 股（回报 6）= 16.0；备选 3+1 股仅得 13.5。
Case 2 · statement-example: skip negative-return strike
输入: [7,[[2,-1,5],[3,4,2]]]
期望: 8
负回报候选不买；只买 2 股成本 3 的，回报 8.0。
Case 3 · typical: small two-strike basic
输入: [6,[[2,1.5,3],[3,2,2]]]
期望: 4.5
Case 4 · typical: cap binds vs budget
输入: [20,[[1,1,5],[2,3,4]]]
期望: 17
Case 5 · typical: ties on per-share return
输入: [10,[[2,2,3],[3,3,2],[5,5,1]]]
期望: 10
Case 6 · boundary: empty candidates
输入: [10,[]]
期望: 0
候选空，返回 0.0。
Case 7 · boundary: budget = 0
输入: [0,[[1,5,10]]]
期望: 0
预算为 0，无法买任何股，返回 0.0。
Case 8 · boundary: empty + budget zero
输入: [0,[]]
期望: 0
Case 9 · boundary: single candidate one share
输入: [5,[[5,3,1]]]
期望: 3
Case 10 · adversarial: all-negative expected returns
输入: [20,[[1,-1,5],[2,-0.5,3],[3,-2,4]]]
期望: 0
所有候选回报为负 -> 持有现金，0.0。
Case 11 · adversarial: every max_shares = 0
输入: [50,[[1,5,0],[2,4,0],[3,3,0]]]
期望: 0
每只候选额度为 0 -> 0.0。
Case 12 · adversarial: cost > budget for all
输入: [3,[[5,100,10],[10,50,5],[4,7,3]]]
期望: 0
所有候选成本都超过预算 -> 0.0。