这是本文档旧的修订版!
给定一个容量为 $m$ 的背包和 $n$ 种物品。每种物品价值为 $v_i$,重量为 $w_i$,数量为 $c_i$。求最多可以得到的价值。
暴力方法为将每种物品转化为 $c_i$ 个独立物品考虑,然后就是一个 $01$ 背包问题。
不难发现任意一个不超过 $c_i$ 的正整数一定用 $1,2,4\cdots 2^n,(c_i-2^{n+1}+1)$ 表示。
于是可以将每种物品拆成 $1,2,4\cdots 2^n,(c_i-2^{n+1}+1)$ 个物品构成的包考虑。
物品总数优化为 $O\left(\sum_{i=1}^n \log {c_i}\right)$,总时间复杂度为 $O\left(m\sum_{i=1}^n \log {c_i}\right)$。