我正在寻找有效的多背包问题的伪代码解决方案(优化语句位于页面的中间)。我认为这个问题是 NP Complete,所以解决方案不需要是最优的,如果它相当有效且易于实施,那将是好的。
问题是这样的:
- 我有许多工作项目,每个项目都需要不同(但固定且已知)的时间来完成。
- 我需要将这些工作项分成组,以便拥有最少数量的组(理想情况下),每组工作项花费的时间不超过给定的总阈值 - 例如 1 小时。
我对阈值很灵活 - 它不需要严格应用,但应该接近。我的想法是将工作项分配到 bin 中,每个 bin 代表阈值的 90%、80%、70% 等等。然后我可以将占 90% 的项目与占 10% 的项目进行匹配,依此类推。
有更好的想法吗?