Knapsack Problem

greedy.js

const items = [{ v: 4, w: 5 }, { v: 2, w: 3 }, { v: 5, w: 6 }];

class Bag {
  constructor(maximumWeight) {
    this.weight = 0;
    this.maximumWeight = maximumWeight;
    this.value = 0;
    this.items = [];
  }

  sum(item) {
    if (this.weight + item.w <= this.maximumWeight) {
      this.weight += item.w;
      this.value += item.v;
      this.items.push(item);
    }
  }

  fits(item) {
    return this.weight + item.w <= this.maximumWeight;
  }

  select(itms) {
    const items = itms.filter(e => this.fits(e));
    let keepSearching = false;
    if (items.length > 0) {
      keepSearching = true;
      let element = items[0];
      for (let i = 1; i < items.length; i++) {
        if (this.fits(element)) {
          const crit = element.v - element.w;
          const crit2 = items[i].v - items[i].w;

          if (crit === crit2) {
            element = element.v > items[i].v ? element : items[i];
          } else {
            element = crit > crit2 ? element : items[i];
          }
        } else {
          element = items[i];
        }
      }
      this.sum(element);
    }
    return keepSearching;
  }
}


// Test

const b = new Bag(37);

let keepSearching = true;
while (keepSearching && b.weight < b.maximumWeight) {
  keepSearching = b.select(items);
}


console.log(b.items);
console.log(b.weight);
console.log(b.value);