时间戳

首页 > 解决方案 > 多约束复杂数据的最佳组合算法

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

问题描述

我想我们可以说这与这里已经提出的问题（Optimisation/knapsack algorithm with multiple constraints 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”等）解决背包问题，这使我能够解决优化单项成本。然后，如果我幸运的话，可以使用这个子集的公共部分并从那里开始工作......但我认为这不是一条好路......

如果您可以提供脚本示例或伪脚本示例，欢迎您！谢谢！

标签： javascriptalgorithmoptimizationcombinationslinear-programming

解决方案

通过检查所有组合的蛮力方法。

function getItems(array, constraints, [optimum, equal]) {
    function iter(index = 0, right = [], add) {

        function update() {
            if (!result.length || optimum(right, result[0])) return result = [right];
            if (equal(right, result[0])) result.push(right);
        }

        if (index >= array.length || !constraints.every(fn => fn(right))) return;
        if (add && right.length) update();

        var temp = right.find(({ ref }) => ref === array[index]),
            old = JSON.parse(JSON.stringify(right));

        if (temp) {
            temp.count++;
        } else {
            right.push({ count: 1, ref: array[index] });
        }

        iter(index, right, true);
        iter(index + 1, old);
    }

    var result = [];
    iter();
    return result;
}

const
    addBy = k => (s, { count, ref: { [k]: value } }) => s + count * value,
    addCount = (s, { count }) => s + count;

// find subset of items that minimize cost, hours and peoples
// and maximize number of items
// do not exceed max values!!!
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 }],
    maxCost = 10000,
    maxHours = 100,
    maxPeoples = 50,
    result = getItems(
        items,
        [
            array => array.reduce(addBy('cost'), 0) <= maxCost,
            array => array.reduce(addBy('hours'), 0) <= maxHours,
            array => array.reduce(addBy('peoples'), 0) <= maxPeoples
        ],
        [
            (a, b) => a.reduce(addCount, 0) > b.reduce(addCount, 0),
            (a, b) => a.reduce(addCount, 0) === b.reduce(addCount, 0)
        ]
    );

console.log(result);
.as-console-wrapper { max-height: 100% !important; top: 0; }

推荐阅读