fast-knapsack v0.1.1

Fast Knapsack (WIP)

Lightweight, flexible, and efficient solution for knapsack problems. This is definitely what you are looking for.

This module provides an algorithm for solving the classic knapsack problem in polynomial time using dynamic programming.

Installation

npm install fast-knapsack --save

Usage

const knapsack = require('fast-knapsack');
const items = {
    'bee': {w: 2, v: 3},
    'cat': {w: 3, v: 4},
    'dog': {w: 5, v: 6}
};

// run by promise
knapsack(items, 6, 'w', 'v')
    .promise()
    .then(res => {
        // success
    })
    .catch(err => {
        // fail
    });

// run by callbacks
knapsack(items, 6, 'w', 'v')
    .callback((err, success) => {
        if (err) {
            // fail
            return;
        }
        // success
    })

API

knapsack (items, limit[, weight, value, count])

Constructs and returns a new object that contains different methods for solving the knapsack problem.

• items: collection of input items for knapsack
  • array (each element is one item)
  • plain JSON object (each key/value is one item)
• limit: maximum weight capacity of knapsack
  • number (representing maximum capacity)
• weight (optional): used for getting the weight of an item
  • number (weight of each item)
  • string (the attribute of the element containing the weight)
  • function (takes in item object and returns the item's weight)
  • default is undefined (assumes all are weighted as 1)
• value (optional): used for getting the value of an item
  • number (value of each item)
  • string (the attribute of the element containing the value)
  • function (takes in item object and returns the item's value)
  • default is undefined, assumes all item's value equals item weight
• count (optional): used for determing how many specific item are remaining.
  • number (count of each item)
  • string (the attribute of the element containing the count)
  • function (takes in item object and returns the item's count)
  • default is undefined, assumes there's only one of each item

promise ()

Returns a promise that gets resolved after completing the knapsack solution.

run (callback)

Input callback gets called once after completing the knapsack solution.