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 중국어 웹사이트의 기타 관련 기사를 참조하세요!