# 优选猫咪：带可行性剪枝的子集搜索

出题人的子集搜索与配套讲解中的剪枝。Codex（GPT-6）：预计算权重、统一 64 位类型及边界验证。程序为 [alternative.cpp](alternative.cpp)，是[动态规划](solution.zh.md)的备用方案，能通过当前完整数据。

## 搜索状态

状态为当前处理位置 $p$ 、已经选择的数量 $j$ 、已有贡献 $s$ ，位置从零开始。若 $j=k$ ，更新最大答案并返回；若剩余 $n-p$ 只猫少于 $k-j$ ，直接返回。否则分支为：

- 选择当前位置，进入 $(p+1,j+1,s+v_p3^{k-j-1})$ .
- 不选择当前位置，进入 $(p+1,j,s)$ .

三的幂提前计算。答案初始为足够小的负数，不能初始为零；当 $k=0$ 时第一个出口立即得到零。

## 正确性与复杂度

每个合法下标集合对应唯一的一条选或不选路径。位置单调增加，所以所选顺序满足题意。新选中的位置是第 $j+1$ 个，因此它的权重为 $3^{k-j-1}$ . 选满以后剩余位置必然不选，可以直接更新答案；剩余数量不足时不存在合法补全，可以剪枝。这两种提前返回不会丢失任何合法最优方案。

二叉决策树至多有 $O(2^n)$ 个节点，每个节点在权重预处理后只做常数工作。总时间为 $O(2^n)$ ，输入、幂数组及递归栈合计 $O(n+1)$ 空间。负数与重复值不改变枚举逻辑。对于更大的 $n$ ，应采用多项式时间的动态规划；本程序的通过结论仅针对当前范围和测量数据。