JS löst das Rucksackproblem basierend auf einem Greedy-Algorithmus

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) // 320

Verwandte 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!