我们先从增长率 r 说起。考过公务员的应该很熟悉 B = A*(1+r)。那么连续增长 n 次,总的倍数就是 (1+r)^n 。现在假定银行年利率非常夸张,为 r = 100%,那么存一年的倍数为 (1+1) = 2,翻了一倍。而如果半年结算一次,那么总倍数变为 (1+0.5)^2 = 2.25,发现倍数变多了。一般的,如果一年结算 n 次,则倍数为 (1+1/n)^n。n 趋于 ∞ 时,其极限是著名的 e,这便是所谓的复利。
这样的论述有一个问题,即为啥把 1 年恰好均分为 n 段,不均分会不会使得倍数更大?也许 (1+0.1)(1+0.2)(1+0.3)(1+0.4) 会比 (1+0.25)^4 更优?
记1年分成任意的n段,增长率分别为 r1、r2、... 、rn。合起来为100%,即 r1+r2+...+rn = 1 。令 y = (1+r1)(1+r2)...(1+rn),求 y 的最大值。
由均值不等式,y ≤ ((1+x1)+...+(1+xn))^n = (1+1/n)^n。当且仅当 r1 = r2 = ... = rn = 1/n 时取等号。
由此看来,均分保证是最优的,而复利公式默认就是均分的。
对于编程选手,计算这个 y 的最大值也有 dp 的做法。(感谢 @有利 给出的方法。)
把它看做完全背包问题。记总容量为V,第 i 个物品的容量为 i、价值为 W(i) = (1+i/V),求装满容量 V 得到的最大价值。f(n) 表示装满容量 n 得到的最大价值。
那么,f(V) = max{ f(V-i)*W(i) },其中 f(0) = 1。
取 V = 10000,可以算出 f(V) = 2.718146,它非常接近 e。这个做法可以求得最大值,但是要解释为啥是 e,需要参考之前纯数学的做法。
对于最大值,按高考数学思维,第一反应是求导分析。而计算机思维看问题的角度又有所不同,换一个角度也许会带来全新的体验。
铺垫完一些概念,我们回到正题。复利的增长率 r = 1/n,而我们酒馆经验的增长率 r 取决于使用的策略。
以常用情形为例,一次放 4 只等级相同的魔物,回收时为 0.7 倍经验。现在考虑当前为 m 级,花费 33.3 小时,我们最多能翻几倍。类似的,可以将 33.3 小时分为若干段。
分为 1 段:一次 33.3 小时,刚好从 1 级升到 m 级,新增了 4 个 m 级。(一次 33.3 小时是指到了 12 小时以后不回收,继续放回升级。如果回收,那就变成 3 段时间了 33.3 = 12 + 12 + 9.3 )
分为 2 段:比如一次 10 小时,一次 23.3 小时。
...
一般的,分为 n 段,此时每段增长率为 ri = 0.7-a^hi,(a = q^-m,公比 q = 1.007,m 是当前等级)
且 h1+h2+...hn = 1,(hi 表示每段用时占总时间 33.3 的比重,且合计为 100%)
类似地,有 y(n) = (1+4r1)(1+4r2)...(1+4rn) ≤ [ 1+4(0.7-a^(1/n)) ]^n
可以代入 n = 1 验证,y(1) ≈ 1 + 4*0.7 ≈ 3.8,即分为 1 段时,倍数为 3.8 倍
和复利类似,只不过 y 的单调性有所变化,n 趋于无穷时,y 反而趋于 0了,这是因为回收只得到 0.7 倍经验,反复过多的利滚利反而把本金亏没了。
上述分析看似很美好,但实际上忽略了底数 a 的变化,a 会随着等级 m 的增大,慢慢的减小。其次,一个问题是认为上一次回收的经验完全用于主力的升级,而忽略了接力狗粮的升级开销,所以实际每段增长率比 ri 略小。修正完这两点以后,最优解会稍稍偏离均分,而是呈现一个类似等差数列的分段形式。
尽管如此,均分为 n 段依然可以作为一个近似解,误差在 1% 以内。至于最优解到底是几小时一次,只需求 y 的极值点,不难推导留作习题。
另外一个常见的策略是阶梯法,放入的4只的等级依次递增。这种情况又有所不同,有待探讨。