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; }