在维基百科的文章关于背包问题包含列表3种它:
1-0(一种类型的项目)
有界的(一种类型的多个项目)
无限(一种类型的项目数量不限)
本文包含针对1.和3.问题类型的DP方法,但没有针对2.的解决方案。
2.如何描述求解动态规划算法?
使用0-1变体,但允许在解决方案中重复其项,直到其界限中指定的次数为止。您将需要维护一个向量,以说明部分解决方案中已包含的每个项目的副本数。