算法设计: can you provide a solution to the multiple knapsack problem?

Question

我正在寻找一个伪代码解决方案来解决 Multiple Knapsack Problem 的问题(优化声明在页面的中间)。我认为这个问题是 NP 完全问题，因此解决方案不需要是最优的，如果它相当有效且易于实现，那将是很好的。

问题是这样的:

• 我有很多工作项目，每个项目都需要不同的(但固定且已知的)时间来完成。
• 我需要将这些工作项目分成几组，以便拥有最少数量的组(理想情况下)，每组工作项目花费的时间不超过给定的总阈值 - 比如 1 小时。

我对阈值持灵活态度 - 它不需要严格应用，但应该接近。我的想法是将工作项分配到容器中，其中每个容器代表阈值的 90%、80%、70% 等等。然后，我可以将占 90% 的项目与占 10% 的项目进行匹配，依此类推。

有什么更好的主意吗？

Answer 1

你需要http://www.or.deis.unibo.it/knapsack.html ，第 6.6 章“多背包问题 - 近似算法”。文本中有伪代码(Pascal 风格)和 Fortran 实现(是的，这是一本旧书)作为 ZIP 文件。