How to parallel Knapsack problems?

3
votes

Knapsack problems is a very famous problem. Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.

This problem can be solved with dynamic programming and can be found on every tutorial book of algorithm. But how can I write a parallel version?

1
algorithmparallel-processingdynamic-programming
What do you mean by parallel version? - shole
I have a lot of item, can I put them on several node and gather the result after that? @shole - maple
This question is not suited for SO - You should have a look at scientific papers mentioning parallel knapsack. With "parallel knapsack problem" I found these slides which propose a multi-core algorithm (I think, did not read). But you will find a lot more results by searching for "knapsack problem on gpu" (e.g. this paper). - Holt

1 Answers

1
votes

That is a very interesting question, the best way to obtain a (good) answer is to use google scholar on such a question. The following link is probably the most recent paper on the subject.