A greedy algorithm for solving the 0/1 Knapsack problem

greedyKnapsack.js

function greedyKnapsack(values, weights, capacity) {
  let n = values.length;
  let ratio = [];
  let totalValue = 0;

  // Step 1: Calculate value-to-weight ratio for each item
  for (let i = 0; i < n; i++) {
    ratio.push({ index: i, value: values[i], weight: weights[i], ratio: values[i] / weights[i] });
  }

  // Step 2: Sort items by descending value-to-weight ratio
  ratio.sort((a, b) => b.ratio - a.ratio);

  // Step 3: Add items to knapsack based on their ratio until capacity is reached
  for (let i = 0; i < n; i++) {
    if (capacity === 0) break; // Knapsack is full
    let item = ratio[i];
    if (item.weight <= capacity) {
      // Item can be fully added
      totalValue += item.value;
      capacity -= item.weight;
      console.log(`Item ${item.index} added completely.`);
    } else {
      // This part would be used in a fractional knapsack, but not applicable in 0/1
      // let fraction = capacity / item.weight;
      // totalValue += item.value * fraction;
      // console.log(`Item ${item.index} added partially: ${fraction * 100}%`);
      // break; // Since this is 0/1 knapsack, we don't add items partially.
    }
  }

  return totalValue;
}

// Example usage
let values = [60, 100, 120];
let weights = [10, 20, 30];
let capacity = 50;

console.log(`Total value in knapsack: ${greedyKnapsack(values, weights, capacity)}`);