算法设计:你能为多背包问题提供解决方案吗？

Question

我正在寻找一个伪代码解决方案,实际上是多个背包问题(优化声明在页面的中间).我认为这个问题是NP Complete,因此解决方案不需要是最优的,而是如果它是相当有效且易于实现的,那将是好的.

问题是这样的:

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

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

有更好的想法吗？

Answer 1

您需要http://www.or.deis.unibo.it/knapsack.html,第6.6章"多个背包问题 - 近似算法".文本中有伪代码(Pascal样式)和Fortran实现(是的,它是一本旧书)作为ZIP文件.