带无限物品的背包

Question

我很熟悉 0-1 背包问题，当你从每件物品中获得一定数量的副本时，但当你使用动态编程为每件物品提供无限数量的副本时，我可以弄清楚如何解决它。我现在正在尝试手动解决它，所以我对任何特定代码都不感兴趣。例如 here 就是我解决 0-1 问题的方法。如果每件物品的副本数量为无限，我需要如何修改？

编辑：我知道对于包含具有相同总值的项目 1、2 和 3 的问题有第二种解决方案。

Answer 1

一种可能性是提供合适数量的多个项目。对于项目 i，最多可以有

m_i := K / w_i

项的选择，其中 K 表示背包容量，w_i 表示第 i 项的重量。此外，对于实例中出现的每个权重值，最多需要一种项目类型，即相对于权重具有最大利润的项目类型。

等效地，可以修改动态程序的评估以反映要采取的不同数量的项目，而不是仅仅区分 0 和 1 的选择。