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

Question

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

有没有任何方法可以解决背包问题，不需要一次增加重量+1。

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

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

Answer 1

仅当自下而上的动态编程实现需要以 1 为步长递增权重。如果自上而下实现它，则只需执行递归调用，同时从剩余容量中减去当前项的权重。