混合背包

问题

有$N$种物品和一个容量为$V$的背包， 每种物品，有的只有一件，有的有多件，有的有无限件。

求最大价值。

思想

多重背包可以通过拆分变成01背包，那么最后问题实际上就是01背包和无限背包的混合。

for i = 1 : n
    if i 为01背包
        for j = V : c[i]
            dp[j] = max(dp[j], dp[j-c[i]] + w[i]);
    if i 为无限背包
        for j = c[i] : V
            dp[j] = max(dp[j], dp[j-c[i]] + w[i]);