你好，想问下这个贪心体现在哪儿呢？这个最优子结构并没有看出来。。。你写的这个证明为什么最大的假设是wi + ai，且后面wi提前这一部分都没看懂，方便说的仔细些吗？
大鱼吃小鱼
changtiaoraplanqiu edited 4 年，5 月前
证明：
只证明$a$为负的情况，最优子结构显然。
假设已经得到最优解,即最小的初始大小为$x$,吃鱼序列为$ w_1, w_2, w_3, ..... w_n$
假设最大的$w + a$为$w_i + a_i$。
若 $i = 1$，证明完毕。
若 $i != 1$，把 $w_i$ 移到最前面得到 $ w_i, w_1, w_2, w_3, …w_i-1, w_i+1.. w_n$ 。下面证明 $x$ 也能成功吃完这个序列。
对于$i+1$之后的序列无需考虑，只需考虑之前的。
因 $x$ 可以吃完原序列，故 $x + \sum_{j = 1}^ia_j > w_i$
若在$1 <= k <= i-1$处停下,即
$x + a_i + \sum_{j = 1}^ka_j < w_{k+1} $
两边加上$a_{k+1}$得
$x + a_i + \sum_{j = 1}^{k+1}a_j < w_{k+1} + a_{k+1} < w_i + a_i$
$x + \sum_{j = 1}^{k+1}a_j < w_i$ 矛盾
所以贪心选择之后仍然是最优解。
Comments
贪心就是吃最大的$w_i+a_i$,实际上这种题只要比较相邻的两项就行了,不相邻的两项可以用冒泡排序的思想.
设体积为x,先吃1再吃2, 要满足的不等式为 $x > w_1, x + a_1 > w_2$
若先吃2再吃1, 要满足的不等式为$x > w_2, x + a_2 > w_1$
如果先吃1更优,等价于能满足第二个不等式一定能满足第一个不等式.
如果满足了第二个不等式,那么$x > w_1 - a_2 > w_1$,所以第一个不等式要考虑的只有$x > w_2 - a_1$
因$w_2 - a_1 > w_2$,所以第二个不等式中有帮助的限制也只有$x > w_1 - a_2$.
到这步就可以发现只要$w_1 - a_2 > w_2 - a_1$,第一个不等式一定能满足
最后结果是先吃$w + a$更大的,在$a$为负数的情况