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

Question

我正在寻找一种伪代码解决方案，来解决多背包问题（优化语句在页面中间）。我认为这个问题是NP完全问题，所以解决方案不需要是最优的，如果它相当高效和易于实现那就好了。

问题如下：

• 我有很多工作项，每个工作项需要不同（但固定和已知）的时间完成。
• 我需要将这些工作项分成组，以便具有最小的组数（理想情况下），每个工作项组的总时间不能超过给定的阈值-例如1小时。

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

还有更好的想法吗？

- MalcomTucker

---

你尝试阅读维基百科页面链接的PDF文件了吗？http://www.diku.dk/hjemmesider/ansatte/pisinger/95-1.pdf（PDF） - Noon Silk

是的，我做了，但我很难理解像“1w e ñ e ð ðñ | y e ðñ ò ñ e ð ó”这样的语句。 - MalcomTucker

好的，那个方法不起作用，但是你明白我的意思。 - MalcomTucker

Answer 1

您需要访问http://www.or.deis.unibo.it/knapsack.html，阅读第6.6章“多重背包问题-近似算法”。书中提供了类似Pascal风格的伪代码，以及Fortran实现（是的，这是一本老书），可以在ZIP文件中找到。

- AVB

---

谢谢您提供的链接，顺便说一句，Martello和Toth都是我在大学时的教授！！！ - Filippo Vitale

Answer 2

据我所知，该问题是NP完全问题（维基百科确认），因此尝试精确解决可能没有太大意义。 然而，有许多方法可能足够好：贪婪算法、遗传算法、模拟退火...其中，贪婪算法可能是最容易实现的：

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

...你明白了。

- Tomislav Nakic-Alfirevic

---

我有以下问题 - https://math.stackexchange.com/questions/2415617。是否有任何贪心算法的方法？ - Royi