标准背包问题的解决方案是 O(nW)，我们将每次增加权重 +1 以获得解决方案。
有没有解决背包问题的方法，不需要一次增加重量+1。
例如我能想到的一种方法是将所有数字除以其公分母
容量 = 100 权重 = [5, 10, 20] -> 容量 = 20 权重 = [1, 2, 4]
最佳答案
只有自下而上的动态规划实现才需要以 1 为步长增加权重。如果你自上而下地实现它，你可以只做一个递归调用，同时从剩余容量中减去当前项目的重量。
关于algorithm - 如何优化0/1背包的解决方案？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/30857389/