changtiaoraplanqiu

changtiaoraplanqiu : 大鱼吃小鱼
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$ 可以 ...查看全文