# 圣辇船直营菓子工房的补货：补充解法

贡献：Codex（GPT-6）补充完全背包建模、证明与程序。答案的按花费分组公式见[首选题解](solution.zh.md)。

初始只有空方案，即 $P_0=1$ ，其余为零。依次处理价格 $i=1,\ldots,X$ ，对花费 $s=i,\ldots,X$ 从小到大执行 $P_s\leftarrow P_s+P_{s-i}$ ，并取模。

处理价格前，数组记录只使用更低价格的方案。对于当前价格，方案分为不购买该商品和至少购买一件两类。前者由当前旧值表示，后者删去一件后对应更新后的较小花费。升序更新允许再次使用当前价格；按价格依次处理则不区分购买顺序。归纳可知，完成后每个位置都是对应花费的方案数，再加权求余款总和即可。

时间 $O(X^2)$ ，空间 $O(X)$ ，零预算为常数工作。该方案不需要数论恒等式，适合作为清楚直接的并列方案；五边形数递推时间阶更低。本题无需展开商品库存，因为预算已经限制了每类购买数量。

程序：[alternative-knapsack.cpp](alternative-knapsack.cpp)。