混合背包 Posted on 2018-09-27 | Edited on 2019-02-12 | In ACM , 动态规划 , 背包相关 | Views: Symbols count in article: 296 | Reading time ≈ 1 mins. 问题有$N$种物品和一个容量为$V$的背包, 每种物品,有的只有一件,有的有多件,有的有无限件。 求最大价值。 思想多重背包可以通过拆分变成01背包,那么最后问题实际上就是01背包和无限背包的混合。 1234567for 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]); Post author: ybmj Post link: http://yoursite.com/2018/09/27/混合背包/ Copyright Notice: All articles in this blog are licensed under BY-NC-SA unless stating additionally.