如何优化 0/1 背包问题的解决方案？

Question

标准背包问题的解决方案为O(nW)，我们会逐步将重量+1以达到解决方案。

是否存在不需要逐步增加重量的背包问题解决方案。

例如，我能想到的一种方法是将所有数字除以它的公共分母。

如下所示：Capacity = 100 weights = [5, 10, 20] -> Capacity = 20 weights = [1, 2, 4]。

- samol

Answer 1

逐步增加权重1只有在自底向上的动态规划实现中才是必要的。如果您实现了自顶向下的方法，可以在递归调用时从剩余容量中减去当前项目的重量。

- Jordi Vermeulen