1/0揹包，如何使它與優先級隊列平行

Question

在1/0揹包問題，可以用兩個for循環動態實現它，像 在這個網站：http://www.bogotobogo.com/Algorithms/knapsack.php

如何與實現它一個優先級隊列並使用多線程優化它？

Answer 1

在「0-1揹包 - 動態規劃」一節中的算法中，內部循環可以並行化。由於m[i][jw]的值的計算不需要值m[i][jw']，其中jw'!=jw，即任何迭代不依賴於先前的迭代，因此對於jw的不同值的循環體的執行可以並行執行。