Skip to content

Instantly share code, notes, and snippets.

View betterkenly's full-sized avatar

Kenly Hui betterkenly

  • San Francisco
View GitHub Profile
@betterkenly
betterkenly / knapsack.js
Created August 9, 2017 23:32 — forked from danwoods/knapsack.js
Knapsack algorithm in JavaScript
//Knapsack algorithm
//==================
// wikipedia: [Knapsack (0/1)](http://en.wikipedia.org/wiki/Knapsack_problem#0.2F1_Knapsack_Problem)
// Given a set `[{weight:Number, benefit:Number}]` and a capacity,
// find the maximum value possible while keeping the weight below
// or equal to the capacity
// **params**:
// `capacity` : Number,
// `items` : [{w:Number, b:Number}]
// **returns**:
/*
A Thief has a knapsack that can hold X lbs of stolen goods
Each stolen good is worth a certain amount of cash, but
the stolen good also weighs a certain weight. This means that
the thief has to pick an optimal combination of items!
The Thief can't pick the same item twice.
What is the maximum worth of goods that the thief can steal?
*/