javascript - 多重约束复杂数据的最佳组合算法

Question

我想我们可以说这与这里已经提出的问题( Optimisation/knapsack algorithm with multiple contraints in JavaScript )非常相似，但尚未得到答案。

假设我们喜欢 javascript、C、C++、java。这些语言中的任何一种都适合我。有人知道解决问题的算法吗？

问题: 在知道资源有限的情况下，找到提供最小成本和最大对象数量的最佳项目子集:

var items = [
    {name: "Rome", cost: 1000, hours: 5, peoples: 5},
    {name: "Venice", cost: 200, hours:  1, peoples: 10},
    {name: "Torin", cost: 500, hours: 3, peoples: 2},
    {name: "Genova", cost: 700, hours: 7, peoples: 8},
    {name: "Rome2", cost: 1020, hours: 5, peoples: 6},
    {name: "Venice2", cost: 220, hours:  1, peoples: 10},
    {name: "Torin2", cost: 520, hours: 3, peoples: 2},
    {name: "Genova2", cost: 720, hours: 7, peoples: 4},
    {name: "Rome3", cost: 1050, hours: 5, peoples: 5},
    {name: "Venice3", cost: 250, hours:  1, peoples: 8},
    {name: "Torin3", cost: 550, hours: 3, peoples: 8},
    {name: "Genova3", cost: 750, hours: 7, peoples: 8}
];
var maxCost = 10000, maxHours = 100, maxPeoples = 50;
// find subset of items that minimize cost, hours and peoples
// and maximize number of items
// do not exceed max values!!!

我的想法:我想我可以为每对成本(让它们称为“KPcost-hours”，“KPhours-cost”，“KPcost-peoples”等)解决背包问题，这给了我优化单一成本的解决方案。然后，如果我幸运的话，可以采用这个子集的共同部分并从那里开始工作...但我认为这不是一条好路...

如果您可以提供脚本示例或伪脚本示例，不客气!谢谢!

Answer 1

通用解决方案

PROBLEM: find the best subset of items which grants minimum cost and maximum number of objects, knowing that there's a limitation of resource.

我在这里看到两个优化标准(我还将在下面讨论您希望最大限度地减少人员、时间和成本的情况)。
一种可能的方法是构建一个将返回最大值 Pareto-optimal set of solutions 的程序。 。

帕累托集是一组非支配解，这意味着对于任何两个解决方案 S1 和 S2，S1 都不占支配地位S2，反之亦然。如果解决方案 S1 在所有标准方面都优于或等于 S2，并且在至少一个标准方面严格优于解决方案 S2，则该解决方案 S1 支配解决方案 S2。

例如，针对您的情况，我们可以考虑以下解决方案:

S1: cost = 10, nb_objects = 4
S2: cost = 10, nb_objects = 7
S3: cost = 0, nb_objects = 0
S4: cost = 14, nb_objects = 6

那么我们的帕累托最优解集就是{S1, S3, S4}。这是因为它们不互相支配(例如，S1 不支配 S4，因为 S4 在对象数量方面更好)。 S2 不是帕累托最优解的一部分，因为它由 S1 和 S4 共同主导。

一般情况下，Pareto 集非常难以计算，并且可能非常大。在您的特定情况下，4 个标准似乎在某种程度上是合理的，但它总是会令人惊讶。
下面是关于如何计算这样一组解决方案的伪代码:

Result = array of size nb_objects, initialized with empty sets
for i from 0 to total_nb_of_objects:
    for each feasible solution 'new_solution' to the problem with fixed number of objects:
        for each solution of Result[i]:
            if hours(new_solution) >= hours(solution) and  \
               cost(new_solution) >= cost(solution) and    \
               people(new_solution) >= people(solution):
                dominated = true
                break
        if not dominated:
            add new_solution to Result[i]
return Result

这里的这个小伪代码对于尝试和理解帕累托效率的概念更有值(value)，我不建议循环背包问题变体的所有可行解决方案(成本太高)。