如何并行解决背包问题？

Question

3

背包问题是一个非常著名的问题。给定一组物品，每个物品都有重量和价值，确定包裹中包含每种物品的数量，使得总重量小于或等于给定限制且总价值尽可能大。

这个问题可以用动态规划来解决，并且可以在每本算法教程书中找到。但是如何编写并行版本呢？

- maple

什么是并行版本？ - shole

我有很多项，我可以把它们放在几个节点上，然后收集结果吗？ @shole - maple

2

这个问题不适合在SO上提问-您应该查阅涉及并行背包的科学论文。使用“parallel knapsack problem”我找到了这些幻灯片，其中提出了一种多核算法（我认为，但没有阅读）。但是，通过搜索“gpu上的背包问题”(例如这篇论文)，您会发现更多结果。 - Holt

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Damien Prot · Accepted Answer

这是一个非常有趣的问题，获得（好的）答案的最佳方法是在谷歌学术上搜索此类问题。以下链接可能是该主题上最新的论文。