8

给定

您有一些非常大量的可能任务，每个任务都需要使用大量可能资源中的一些可能资源子集。

每个任务都有一个相关的资源成本：

任务1

  • 1金
  • 2银

任务 2

  • 2金
  • 1 青铜

任务 3

  • 1 青铜

你有一组可用的资源：

资源

  • 3金
  • 2 青铜

问题

选择一个任务子集，其中任何一个都可以执行多次，以“最佳利用”所有可用资源。在这种情况下，也许我们会选择任务 2 和任务 3，因为它只剩下 1 个金币。我们无法执行任务 1，因为我们没有银子。

问题

这似乎是某种优化问题，但我完全不确定这个问题会被“称为”什么。是否有一些花哨的名字可以用来指导我寻找可能的解决方案？是否有直接的算法可以解决这个问题？是否可以在合理的时间内解决？有一些好的启发式方法吗？

笔记

  • 所示问题意味着资源的权重可能不同（即留下 1 枚金币比留下 1 枚铜牌更糟糕），但这不一定是问题。解决方案不能解释这一点，但它会是一个有趣的扩展。
  • 任务和资源不必是整数值，但我不确定这是否会显着改变问题。
4

2 回答 2

8

这听起来就像一个多重背包问题 - 您唯一需要更改的是为每个项目分配等于它使用的项目总和的值，然后它变成一个标准背包，因为在最大化总和的同时，其余部分被最小化.

于 2013-06-14T15:00:50.063 回答
2

这个问题是一种集装式。它也被称为“机组人员问题”。你有一定数量的飞行员、工程师、乘务员等，以及需要不同类型机组人员的不同飞机。通常对于机组人员问题，您正在寻找人员和飞机之间的精确分配，但在这里我们希望通过选择不同类型的飞机（即帖子中的“任务”）来最大化人员利用率。

在任何情况下，解决这些NP-hard问题的方法是使用混合整数线性规划进行穷举搜索。请参阅MILP 的 Sandia 调查或MILP上的 MIT Aeronautics 页面。

有一个包SYMPHONY，其中包括执行此操作的集合分区和打包求解器。

于 2013-06-14T15:46:33.337 回答