大鱼吃小鱼

changtiaoraplanqiu edited 10 月,2 周前

证明:
只证明$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

ctttttry

你好,想问下这个贪心体现在哪儿呢?这个最优子结构并没有看出来。。。你写的这个证明为什么最大的假设是wi + ai,且后面wi提前这一部分都没看懂,方便说的仔细些吗?

changtiaoraplanqiu

贪心就是吃最大的$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$为负数的情况

你当前正在回复 博客/题目
存在问题!