如何優化0/1揹包的解決方案？

Question

標準揹包問題解決方案是O(nW)，我們將一次增加權重+1以獲得解決方案。

是否有任何解決揹包問題的方法，一次不需要遞增權重+1。

例如我能想到的一種方式是通過其共同點

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

Answer 1

在遞增步長爲1的權重，以所有的數字鴻溝只需要一個自下而上的動態規劃的實施。如果您自上而下地實施它，則可以在從剩餘容量中減去當前項目的權重的同時執行遞歸調用。