我应该使用哪种优化算法来最大限度地利用时间限制？

Question

我想找到一个合适的算法来解决这个问题:

假设我们有N个项目,我们知道每个项目将获得多少资金,以及每个项目需要多少时间(每个项目的预计时间).我们有一定的时间来完成所有项目.我们希望选择项目以使我们的利润最大化,并且总体估计时间不会超过可用时间.你能告诉我应该使用哪种优化算法吗？有没有我可以在C#,.NET技术或Java技术中使用的东西？

Answer 1

这听起来像直截了当的背包问题:

给定一组具有权重和值的项目,确定要包括在集合中的每个项目的计数,使得总权重小于或等于给定限制,并且总值尽可能大.

在您的情况下,权重是项目所需的时间,限制是时间限制.

通常情况下,如果你是为现实世界做这件事,那么对于小案例来说蛮力就足够了,如果你真的不关心准确的最大值,那么对于大的情况,贪婪的近似和一些随机化应该足够好.但是,我怀疑是否有人会在现实世界中使用如此严格的模型.

在理论上感兴趣的情况下,背包问题是NP难的,并且是算法的活跃领域.