题目链接：
http://poj.org/problem?id=3040
https://www.lydsy.com/JudgeOnline/problem.php?id=1685
某普及模拟赛搬了这题，题解是贪心，我不会证还找不到证明。于是想了挺久然后证出来了。
贪心做法：
每次选出一个体积和 $\ge C$ 的物品集合，直到剩下物品体积和不足 $ < C $ 为止。
每次选择方法：
1.按 $v$ 从大到小枚举每个物品，在保证体积和 $< C $ 的情况下能选多少选多少。
2.将还存在的 $v$ 最小的物品加入选择的集合。显然加了之后体积和 $\ge C$ 。
证明：
假设 $v_{1..n}$ 递增。
首先，如果在第二步中选择的物品不是 $1$ ，设它为 $i$ 。
设第一步中选择的 $i..n$ 的物品的体积和为 $k v_i$ ， $1..i-1$ 的和为 $z$ 。
由第一步的定义得 $k v_i +z < C$ 。
因为第一步枚举到 $i$ 的时候没有多选一个 $i$ ，所以 $(k+1) v_i \ge C$ 。
因此体积和是否 $\ge C$ 跟物品 $1..i-1$ 无关，可以把他们都丢掉，即只考虑物品 $i..n$ 。
这样操作后第二步选择的物品就一定是 $1$ 了。
然后，将所有 $v_i$ 变成 $\displaystyle \frac{v_i}{v_1}$，并将 $C$ 变成 $\lceil \displaystyle \frac{C}{v_1} \rceil$ ，这样操作就使得 $v_1=1$ 。
于是可以发现，第一步选的物品体积和恰为 $C-1$ ，第二步之后物品体积和恰为 $C$ 。
用 $f_{1..n}$ 来描述一个物品集合，表示这个集合中物品 $i$ 有 $f_i$ 个。
假设贪心法得到的下一个选择为 $f$ ，但下一个选择为 $g$ 能得到更优的答案(称 $g$ 为反例)。
令 $p=\max\{i|f_i \not= g_i\}$ 。
情况 $1:$ $g_p < f_p$
因为 $\sum_{i=1}^{n} f_i v_i=C$,$\sum_{i=1}^{n} g_iv_i \ge C$ ，所以 $\sum_{i=1}^{n} g_iv_i \ge \sum_{i=1}^{n} f_iv_i$
所以 $\sum_{i=1}^{p} g_iv_i \ge \sum_{i=1}^{p} f_iv_i$ ，又因为 $g_p < f_p$ ，所以 $\sum_{i=1}^{p-1}g_iv_i \ge \sum_{i=1}^{p-1}f_iv_i+v_p$ 。
所以 $\sum_{i=1}^{p-1}g_iv_i \ge v_p$ 。
那么就一定能选出一个 $g_{1..p-1}$ 的子集 $s$ 满足和为 $v_p$ ，归纳一下就可以证明。
显然不选 $s$ 而多选一个 $p$ 肯定更优。
那么由 $g$ 为反例就可以推出 $g-s+\{p\}$ 为反例。归纳证明即可。
情况 $2:$ $g_p >f_p$
由第一步 $p$ 没有多选一个知 $\sum_{i=p}^{n} f_iv_i+v_p \ge C$
那么不妨令 $g_{1..p-1}=0,g_p=f_p+1$ ，因为由 $g$ 为反例可以推出这样操作后的 $g$ 为反例。
那么既然现在 $1..p-1$ 都不用，那么不妨令以后也都不用了，不然就会得到一个最小非零元素更小的反例，归纳证明即可。
那么只用 $p..n$ 的话 $f$ 显然优于 $g$ ，因为少用了一个 $p$ 。
因此就证完了。
鄂公网安备 42010202000505 号