算法设计：可以为多背包问题提供解决方案吗？ [英] Algorithm design: can you provide a solution to the multiple knapsack problem?

问题描述

我正在寻找一个伪代码解决方案，以实现有效的多重背包问题 （优化说明是页面的一半）。我认为，这个问题是NP Complete，所以解决方案不需要是最优的，而是如果它是相当有效和容易实现的，那将是好的。

I am looking for a pseudo-code solution to what is effectively the Multiple Knapsack Problem (optimisation statement is halfway down the page). I think this problem is NP Complete so the solution doesn't need to be optimal, rather if it is fairly efficient and easily implemented that would be good.

问题是这样的：

• 我有很多工作项，每个采取不同（但固定和已知）的时间来完成。


• 我需要将这些工作项分成组，以使组数最少（理想情况下），每组工作项不超过给定的总阈值 - 例如1小时。

我对门槛很灵活 - 它不需要刚性应用，尽管应该很接近。我的想法是将工作项目分配到每个bin代表阈值的80％，80％，70％等等的bin中。我可以匹配那些占10％的用户的90％的项目，等等。

I am flexible about the threshold - it doesnt need to be rigidly applied, though should be close. My idea was to allocate work items into bins where each bin represents 90% of the threshold, 80%, 70% and so on. I could then match items that take 90% to those that take 10%, and so on.

任何更好的想法？

推荐答案

您需要 http：// www .or.deis.unibo.it / knapsack.html ，第6.6章多重膝关节问题 - 近似算法。文本中有伪代码（Pascal样式）和Fortran实现（是的，这是一本旧书）作为ZIP文件。

You need http://www.or.deis.unibo.it/knapsack.html, chapter 6.6 "Multiple knapscack problem - Approximate algorithms". There is pseudo-code (Pascal style) in the text and Fortran implementations (yes, it's an old book) as a ZIP file.

这篇关于算法设计：可以为多背包问题提供解决方案吗？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！