确定资源分配需要的算法

Question

我试图自动完成一项任务，但我缺乏正确的词汇表来查找正确的算法。这真的感觉像一个常见的问题，很可能已经解决了很多次。

我所要找的只是找个人为我指出正确的方向，或者帮助我找到合适的搜索词来查找一个解决方案/算法。如果你碰巧知道一个actuall库(javascript)，那就更好了。

虚构的场景

假设我有3个‘桶’，Bucket A，Bucket B和Bucket C。每一个都能容纳一定数量的“球”。

• Bucket A：容量10球。
• Bucket B：可容纳15个球。
• Bucket C：容量5球。

现在，我也有一个球的清单，每一个只能放在特定的‘桶’。一个球只能进入Bucket 2，下一个球可以进入Bucket 1或Bucket 3，依此类推。

现在.。我需要确定最好的方式放置球，以尝试填补每一个‘桶’的容量(或尽可能接近)。

真实场景

我这样做的真正原因是为了安排people (球)访问locations (桶)所需的时间(桶的容量)。但是，由于以下原因，我在搜索“调度”时发现的所有库/算法在我的场景中都不起作用。

• 我根本不关心开始/结束的时间，只有person -> location
• 我的人(球)都有一个严格的名单，他们可以访问的地点。每一个都是独一无二的。
• 每个人都可以在一个location上花费任意数量的整个(整数)小时。使用的人，8小时，其中只有7个小时是可以的。
• 每一个地点(桶)都需要一定的时间，我试着尽我最大的能力与任何组合的人一起工作。

我有大约50个地点和100个人。这不是要求我得到一个完美的解决方案，而是“非常接近”。

我发现schedule.js看起来棒极了，但我一直无法滥用它来满足我的需求。

Answer 1

如果每个人可用的小时数是常数(例如，它总是1小时)，那么您的问题可以建模为一个网络流，很容易在多项式时间内用福特-富尔克森算法求解。

要构建您的流网络，创建两层节点；第一层表示您的球，第二层表示您的桶。在每个容量为1的球上添加一个从源到每个球的边缘。在每个容量为1的兼容桶中添加一个边缘。从每个水桶中添加一个边缘到水槽，其容量与桶容量相对应。最大流量代表最优分配。

否则，如果每个人可以贡献的小时数不同，则由于您的限制，每个人只能访问一个位置，上述算法无法工作。(网络流量可以解决这个问题，但它可能会将一个人的工作时间分散在多个地点。)在本例中，您有一些与背包或垃圾箱包装问题相关的内容。

如果每个人可以贡献的小时数是一个整数，则可以通过伪多项式动态规划来求解。否则，你必须：

1. 实现蛮力回溯算法。这将给你一个确切的解决方案，但如果人数或地点超过50人左右，将无法工作。
2. 正如布朗博士所建议的那样，实现一种组合启发式方法。对于这个问题，爬山或模拟退火会表现得很好，并且会很快给出最优或几乎最优的结果。