Zuvor haben wir über die Verwendung eines gierigen Algorithmus zur Lösung des Änderungsproblems durch JS berichtet. In diesem Artikel stellen wir Ihnen vor, wie JS das Rucksackproblem basierend auf einem gierigen Algorithmus löst.
Gieriger Algorithmus: Treffen Sie bei der Lösung eines Problems immer die im Moment beste Wahl. Mit anderen Worten, ohne die Berücksichtigung der insgesamt optimalen Lösung war das, was er machte, in gewissem Sinne nur eine lokal optimale Lösung. Der Prozess der optimalen Lösungsfindung zielt darauf ab, die aktuell optimale Lösung zu erhalten.
Einige Rucksackprobleme: Der maximale Gesamtwert der Gegenstände, die in einem Rucksack mit festem Volumen untergebracht werden können
Artikel A B C D
Preis 50 220 60 60
Größe 5 20 10 12
Verhältnis 10 11 6 5
Geben Sie so viele Elemente wie möglich in absteigender Reihenfolge der Proportionen ein
function greedy(values, weights, capacity){
var returnValue = 0
var remainCapacity = capacity
var sortArray = []
values.map((cur, index) =>{
sortArray.push({
'value': values[index],
'weight': weights[index],
'ratio': values[index]/weights[index]
})
})
sortArray.sort(function(a, b){
return b.ratio > a.ratio
})
console.log(sortArray)
sortArray.map((cur,index) => {
var num = parseInt(remainCapacity/cur.weight)
console.log(num)
remainCapacity -= num*cur.weight
returnValue += num*cur.value
})
return returnValue
}
var items = ['A','B','C','D']
var values = [50,220,60,60]
var weights = [5,20,10,12]
var capacity = 32 //背包容积
greedy(values, weights, capacity) // 320Verwandte Empfehlungen:
Wie man Greedy im JS-Algorithmus verwendet, um das Änderungsproblem zu lösen
PHP implementiert das Gier-Algorithmus-0-1-Rucksackproblem
Beispielanalyse zur Implementierung des Rucksackalgorithmus in Java
Das obige ist der detaillierte Inhalt vonJS löst das Rucksackproblem basierend auf einem Greedy-Algorithmus. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!
