从酒馆经验到金融复利

酒馆机制是一个现实中非常常见的模型，从银行存款利息到房贷都有类似的影子。比如说房贷，30年利滚利，发现最后还款总额是当初借钱的两倍之多。

我们先从增长率 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只的等级依次递增。这种情况又有所不同，有待探讨。