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

Question

标准背包问题解决方案是O(nW)，我们将一次增加权重+1以获得解决方案。

是否有任何解决背包问题的方法，一次不需要递增权重+1。

例如我能想到的一种方式是通过其共同点

Capacity = 100 weights = [5, 10, 20] -> Capacity = 20 weights = [1, 2, 4]

Answer 1

在递增步长为1的权重，以所有的数字鸿沟只需要一个自下而上的动态规划的实施。如果您自上而下地实施它，则可以在从剩余容量中减去当前项目的权重的同时执行递归调用。