1/0 Knapsack, how to make it parallel with priority queue [closed]

Question

Closed. This question needs to be more focused. It is not currently accepting answers.

---

Want to improve this question? Update the question so it focuses on one problem only by editing this post.

Closed 9 years ago.

Improve this question

In 1/0 Knapsack Problem, one can implement it dynamically with two for loops, like on this site: http://www.bogotobogo.com/Algorithms/knapsack.php

How can i implement it with a priority queue and optimize it with multithreading?

Answer 1

In the algorithm in the section "0-1 Knapsack - Dynamic Programming", the inner loop can be parallelized. The execution of the loop's body for different values of jw can be executed in parallel as the calculation of the value for m[i][jw] does not require values m[i][jw'] where jw'!=jw, i.e. any iteration does not depend on previous iterations.