混合背包

问题

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

求最大价值。

思想

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

1
2
3
4
5
6
7
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]);
Thank you for your support!