混合背包

问题

---

给定$n$个物品和一个容量为$W$的背包，对于第$i$个物品有重量$w[i]$和价值$v[i]$，其中有的物品数量为$cnt[i]$，有的物品数量不限。选择若干个物品放入背包中，在不超过背包最大容量的情况下，求背包中物品价值之和的最大值。

过程

---

多种背包混合的问题，依旧设$dp[i][j]$为前$i$个物品在背包容量为$j$的情况下所能达到的最大总价值。
根据$i$的数量分别选择不同背包模型即可。
滚动数组优化：注意到$dp[i][]$只需要$dp[i][]$和$dp[i-1][]$，因此可以去掉第一维并不断更新自身实现空间。

实现

---

题目

---