algorithm - 算法设计：你能提供多背包问题的解决方案吗？

Question

我正在寻找有效的多背包问题的伪代码解决方案（优化语句位于页面的中间）。我认为这个问题是 NP Complete，所以解决方案不需要是最优的，如果它相当有效且易于实施，那将是好的。

问题是这样的：

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

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

有更好的想法吗？

Answer 1

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

Answer 2

据我所知，这个问题是 NP 完备的（维基百科确认），所以试图完全解决它可能没有多大意义。但是，任何数量的方法都可能对您来说足够好：贪婪，遗传算法，模拟退火......贪婪可能是最容易实现的：

while (time available in block greater than smallest task duration)
  find the longest fitting task
  add it

...你明白了。