挖坑。

https://gist.github.com/lychees/6b77182120f681429f8f

http://blog.brucemerry.org.za/

## Problem B. Buffed Buffet

### Brief description:

多重背包、凸背包。

有兩類物品可供選擇，離散和連續。

對於連續的物品，初始單位容量的價值為 `t`

、單位容量價值損失的速率為 dt。

對於離散的物品，每份物品的容量是 `w`

、初始每份物品的價值為 `t`

、每選擇一個物品，下一個件物品價值損失的速率為 `dt`

。

問恰好裝滿 `m`

容量時的最大價值。

### Analysis:

$$! \begin{aligned}g'(i) &= \max_{0 \le j \le i}\big\{ g(j) + \sum_{n=1}^{i-j}(t – (n-1)d\big\}\\&= \max_{0 \le j \le i}\big\{ g(j) + (i-j)t – \frac{(i-j-1)(i-j)}{2}\cdot d\big\}\\&= \max_{0 \le j \le i}\big\{ g(j) + (i-j)t – \frac{i(i-1)+j(j+1)-2ij}{2}\cdot d\big\}\\&= it – \frac{i(i-1)d}{2} + \max_{0 \le j \le i}\big\{ g(j)-\frac{j(j+1)d}{2} – jt + ijd\big\}\\&= it – \frac{i(i-1)d}{2} + \max_{0 \le j \le i}\big\{ h(j) + ijd \big\}\end{aligned}$$