Finden Sie die beste Kombination mit niedriger Kosten

Question

Ich habe ein Array wie folgt:

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

Ich mag wie das Ergebnis erhalten:

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

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

Hier 7, 9 sind Eingangswert

Wie löst es dieses Problem?

Answer 1

Sie könnten durch die Gruppen der Gebühr iterieren und den ganzzahligen Wert der Zählung erhalten, die möglich ist. Speichern Sie den Wert und fahren Sie fort, bis alle Gruppen markiert sind.

Das Array, das iteriert wird, muss zuerst nach den niedrigsten Kosten, dann nach höheren Kosten und nach größeren Paketen sortiert werden.

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

Answer 2

Dieser ist ein bisschen schwierig, aber das funktioniert und ist scaleble:

var arr = [10, 18, 32, 60]; 
var search = 7; 
var result = 0; 

for (var i = 0; i < (search >>> 0).toString(2).length; i++) { 
    if ((search >>> 0).toString(2)[i] == "1") { 
     result += arr[i]; 
    } 
} 
// result = 60 

Erläuterung: Der (search >>> 0).toString(2) wandelt den seached Wert (7) in eine binäre Maske. 7 => 111 und 9 => 1001. Dann durchläuft es jedes Zeichen dieser binären Zeichenfolge und prüft, ob es eine 0 oder 1 ist und fügt dem Ergebnis das Äquivalent aus dem Array hinzu.