Maison > interface Web > js tutoriel > le corps du texte

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

小云云
Libérer: 2017-12-07 15:57:58
original
1987 Les gens l'ont consulté

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
Copier après la connexion

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!

Étiquettes associées:
source:php.cn
Déclaration de ce site Web
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn
Tutoriels populaires
Plus>
Derniers téléchargements
Plus>
effets Web
Code source du site Web
Matériel du site Web
Modèle frontal