JS は欲張りアルゴリズムに基づいてナップザック問題を解決します

以前、貪欲アルゴリズムを使用して変更問題を解決する JS について共有しました。この記事では、JS が貪欲アルゴリズムに基づいてナップザック問題を解決する方法を紹介します。

貪欲なアルゴリズム: 問題を解決するときは、常に現時点で最善の選択をしてください。つまり、彼が作ったのは全体最適解を考慮せず、ある意味局所最適解に過ぎなかったのである。最適解を見つけるプロセスは、現在の最適解を取得することを目的としています。

バックパックの問題の一部: 一定容量のバックパックに入れることができるアイテムの最大値の合計

アイテム A B C D
価格 50 220 60 60
サイズ 5 20 10 12
比率 10 11 6 5

割合の高い順にできるだけ多くの項目を入れてください

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

関連する推奨事項:

JS が貪欲アルゴリズムを使用して変更問題を解決する方法

php は貪欲アルゴリズム 0-1 ナップザック問題を実装します

Java がナップサックアルゴリズムを実装する方法のインスタンス分析

以上がJS は欲張りアルゴリズムに基づいてナップザック問題を解決しますの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。