JS résout le problème du sac à dos grâce à un algorithme glouton

Plus tôt, nous avons parlé de l'utilisation par JS d'un algorithme glouton pour résoudre le problème du changement. Dans cet article, nous vous présenterons comment JS résout le problème du sac à dos basé sur un algorithme glouton.

Algorithme gourmand : Lors de la résolution d'un problème, faites toujours le meilleur choix du moment. En d’autres termes, sans considérer la solution optimale globale, ce qu’il a fait n’était qu’une solution optimale locale dans un certain sens. Le processus de recherche de la solution optimale vise à obtenir la solution optimale actuelle.

Quelques problèmes de sac à dos : La valeur maximale totale des articles pouvant être placés dans un sac à dos à volume fixe

Article A B C D
Prix 50 220 60 60
Taille 5 20 10 12
Ratio 10 11 6 5

Mettre autant d'articles que possible par ordre décroissant de proportion

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

Recommandations associées :

Comment utiliser l'algorithme gourmand dans JS pour résoudre le problème du changement

PHP implémente l'algorithme gourmand 0-1 problème de sac à dos

Exemple d'analyse de la façon d'implémenter l'algorithme de sac à dos en Java

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!