预算约束下的标的选择（0/1 背包）

组合经理手头有固定的现金预算和一份筛选后的标的池。每个标的最多买一股、单股成本是已知整数；研究模型给每个标的标了一个整数的预期利润。她想找一个标的子集——每个买一股——使总成本不超预算、总预期利润最大。这是经典 0/1 背包 问题：每个标的是 yes/no 决策（不允许分数股、不允许同一标的买两份），cost 是重量、profit 是价值、现金预算是容量。

请实现 solution(items, budget)。items 是 dict 列表 {"symbol": str, "cost": int, "profit": int}，budget 是非负整数。返回 dict {"max_profit": int, "selected": list[str]}，其中 selected 是被选中的 symbol 排序后列表。

当多个子集都能达到最大利润时，tie-break 规则：取字典序最小的排序后选中列表 —— 按 symbol 升序顺序处理物品，只要纳入它后剩余物品仍能在剩余预算内凑齐最大利润目标，就纳入它。 这一规则确定性、可重现，并匹配「利润相同时偏好包含字典序更小符号的子集」的直觉。

示例

solution([{"symbol": "NVDA", "cost": 2, "profit": 3}, {"symbol": "MSFT", "cost": 3, "profit": 4}, {"symbol": "TSLA", "cost": 4, "profit": 5}, {"symbol": "AMZN", "cost": 5, "profit": 6}], 5) 返回 {"max_profit": 7, "selected": ["MSFT", "NVDA"]}。经典小背包：成本 2+3=5 恰好等于预算，利润 3+4=7，比任意单一物品（单标的最大利润 6 来自成本为 5 的 AMZN）都好。

solution([{"symbol": "AAPL", "cost": 300, "profit": 50}, {"symbol": "GOOG", "cost": 250, "profit": 40}], 100) 返回 {"max_profit": 0, "selected": []}。两个标的的成本都超预算，无法买入；最优是持币不动，利润 0、选中集为空。

solution([{"symbol": "ZZZZ", "cost": 5, "profit": 10}, {"symbol": "AAAA", "cost": 5, "profit": 10}], 5) 返回 {"max_profit": 10, "selected": ["AAAA"]}。预算只够买一个，两个候选利润相同 → tie-break 选字典序更小的 AAAA。

函数骨架见 stubs/stub.py。

应用背景

预算约束下的子集选择是组合构建的核心问题：每个零售券商 App、每个 robo-advisor 的开户引导、每个 PM 的资产配置工具，归根到底都在回答某种形态的「给定我的现金和一份候选清单，开哪些仓？」此处的 0/1 背包归约（每个标的 1 股、整数成本和利润、硬预算上限）刻意做了简化 —— 真实生产组合优化器还要叠加分数股、最小手数、行业上限、交易成本、Beta 中性、换手率惩罚等。但这个最简形态恰好是面试白板题的基本骨架，也是更复杂优化器的内核：dp 递推完全相同，只是状态空间变大。Tie-break 取字典序最小不只是装饰 —— 生产系统要求确定性输出，相同输入跨重跑、跨审计、跨单测必须给出一致的选股结果，这也是「先按符号排序、再回溯 dp」这个习惯值得养成的原因。掌握了这套二维 dp + traceback 的骨架，多重背包（行业桶）、有界背包（最小手数）、value-cost-ratio 贪心给 branch-and-bound 当上界等扩展，都能水到渠成。