题目链接:
http://poj.org/problem?id=3040
https://www.lydsy.com/JudgeOnline/problem.php?id=1685
某普及模拟赛搬了这题,题解是贪心,我不会证还找不到证明。于是想了挺久然后证出来了。
贪心做法:
每次选出一个体积和
每次选择方法:
1.按
2.将还存在的
证明:
假设
首先,如果在第二步中选择的物品不是
设第一步中选择的
由第一步的定义得
因为第一步枚举到
因此体积和是否
这样操作后第二步选择的物品就一定是
然后,将所有
于是可以发现,第一步选的物品体积和恰为
用
假设贪心法得到的下一个选择为
令
情况
因为
所以
所以
那么就一定能选出一个
显然不选
那么由
情况
由第一步
那么不妨令
那么既然现在
那么只用
因此就证完了。