JS solves the knapsack problem based on greedy algorithm

Earlier we shared about JS using greedy algorithm to solve the change problem. In this article, we will introduce to you how JS solves the knapsack problem based on greedy algorithm.

Greedy Algorithm: When solving a problem, always make the best choice at the moment. In other words, without considering the overall optimal solution, what he made was only a local optimal solution in a certain sense. The process of finding the optimal solution aims to obtain the current optimal solution.

Some backpack problems: The total maximum value of items that can be placed in a backpack with a fixed volume

Item A B C D
Price 50 220 60 60
Size 5 20 10 12
Ratio 10 11 6 5

Put as many items as possible in descending order of 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

Related recommendations:

How to solve the problem using greedy algorithm in JS Change problem

php implementation of greedy algorithm 0-1 knapsack problem

Instance analysis of how to implement knapsack algorithm in Java

The above is the detailed content of JS solves the knapsack problem based on greedy algorithm. For more information, please follow other related articles on the PHP Chinese website!