较为形式化的贪心策略证明

设最优解中购买的宝石集合为 $B$，免费获得的宝石集合为 $F$，满足 $|F| \le k\land \sum_{i \in B} w_i \le W$，目标最大化总美丽度 $\sum_{i \in B} v_i + \sum_{i \in F} v_i$。

假定此时一组不做任何相对花费约束的集合 $B$ 和 $F$ 是使总美丽度取最大值的合法解。

交换调整：若存在 $a \in B$ 和 $b \in F$ 使得 $w_a > w_b$，则考虑交换二者的身份：让 $a$ 变为免费，$b$ 变为购买。新的购买集合 $B' = (B \setminus \{a\}) \cup \{b\}$，新免费集合 $F' = (F \setminus \{b\}) \cup \{a\}$。此时总花费变为

因为 $w_b < w_a$。总美丽度不变，故新解仍为最优解。重复此交换过程，直到不存在这样的逆序对。最终得到的解中，所有购买宝石的价格都不大于任何免费宝石的价格，即若 $i \in B$，$j \in F$，则必有 $w_i \le w_j$。

由排序性质可知，存在一个分界点 $p$，使得所有购买宝石的编号不超过 $p$，所有免费宝石的编号大于 $p$（价格相等时编号大小关系可任意，不影响结论）。因此，最优解可以描述为：先选取某个分割点 $i$（$0 \le i \le n$），在前 $i$ 个宝石中用 $W$ 元进行购买（01背包），在后 $n-i$ 个宝石中免费取至多 $k$ 个美丽度最大的宝石。

该贪心策略的正确性得证。