javascript - 以更低的成本找到最佳组合

Question

我有一个像这样的数组:

fee=[1 => 10,2=>18,4=>32,8=>60]

我想要得到如下结果:

7 -> 4+2+1 => 32+18+10
7=>60

9  -> 8+1 => 60+10
9=>70

这里7、9是输入值

如何解决这个问题？

Answer 1

您可以遍历费用组并获取可能的计数整数值。保存该值并继续，直到检查完所有组。

迭代的数组必须首先按最低成本排序，然后按较高成本排序，最后按较大包排序。

function getLowestCost(value, fee) {
    var result = { cost: 0 };

    result.rest = Object.keys(fee).sort(function (a, b) {
        return fee[a] / a - fee[b] / b || b - a;
    }).reduce(function (r, a) {
        result[a] = Math.floor(r / a);
        result.cost += result[a] * fee[a];
        return r % a;
    }, value);

    return result;
}

console.log(getLowestCost(7, { 1: 10, 2: 18, 4: 32, 8: 60 }));
console.log(getLowestCost(9, { 1: 10, 2: 18, 4: 32, 8: 60 }));

console.log(getLowestCost(7, { 1: 10, 2: 20, 4: 32, 8: 60 }));
console.log(getLowestCost(9, { 1: 10, 2: 20, 4: 32, 8: 60 }));

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