给定多种类型的资源和每项任务的特定资源混合,最大限度地提高资源利用率

Question

特定

您有一些非常大量的可能任务,每个任务都需要使用来自大量可能资源的某些可能资源子集.

每项任务都有相关的资源成本:

任务1

• 1金
• 2银

任务2

• 2金
• 1铜

任务3

• 1铜

你有一套可用的资源:

资源

• 3金
• 2青铜

问题

选择任务的子集,其中任何一个都可以执行多次,这样可以"充分利用" 所有可用资源.在这种情况下,也许我们会选择任务2和任务3,因为它只剩下1金.我们不能执行任务1因为我们没有白银.

问题

这似乎是某种优化问题,但我不确定这个问题会被"称为".是否有一些奇特的名字,我可以抬头指导我寻找可能的解决方案？那里有直接的算法可以解决这个问题吗？它能在合理的时间内解决吗？有一些很好的启发式方法吗？

笔记

• 如图所示的问题意味着资源的权重可能会有所不同(即,留下1金币比使用1铜牌更糟糕),但这不一定是个问题.解决方案必须不考虑这一点,但这将是一个有趣的扩展.
• 任务和资源不必是整数值,但我不确定这是否会显着改变问题.

Answer 1

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