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!