ukp

ukp

Solve the unbounded knapsack problem and its dual version.

The original UKP tries to find the maximum value of Σ v_i x_i subject to Σ w_i x_i ≤ W, and the dual version tries to find the minimum value of Σ v_i x_i subject to Σ w_i x_i ≥ W, where 1 ≤ i ≤ n and

• w_i ≥ 0 is the weight of the i-th item,
• v_i ≥ 0 is the value of the i-th item, and
• x_i = 0, 1, 2, 3, … is the number of copies of the i-th item.

When x_i is unbounded for all the items, this module solves both problems in 𝒪(W) time, for a fixed n. Whether it is 𝒪(n) for a fixed W or not is not tested (yet).

Using this module you can also limit the number of copies of some items. However, due to bad optimization, this may drop the cache hit rate by a significant amout and affect the performance drastically.

Usage

npm install ukp

ukp(W, items)

var ukp = require('ukp');

ukp(11, [
    {name: 'a', weight: 2, value: 10, count: 2},
    // `count` defaults to Infinity if omitted
    {name: 'b', weight: 3, value: 11},
    // name, weight, value in that order
    ['c', 4, 19],
    // name, weight, value, count in that order
    ['d', 0, 0, Infinity]
]);

Output

{ counts: { a: 2, b: 1, c: 1 }, weight: 11, value: 50 }

If the value is the same this function picks the one with a smaller weight.

ukp.dual(W, items)

// Same thing goes for the dual version
ukp.dual(11, [
    {name: 'a', weight: 2, value: 10, count: 2},
    {name: 'b', weight: 3, value: 11},
    ['c', 4, 19],
    ['d', 0, 0, Infinity]
]);

Output

{ counts: { a: 1, b: 3 }, weight: 11, value: 43 }

If the value is the same this function picks the one with a larger weight. Returns false if the condition is unsatisfiable.

Limitations

• The algorithm is not optimized properly so it may rather be slow.
• Call stack may overflow if the recursion gets too deep.
• Using non-integer values for the weights and the values may result in an incorrect answer.
• This module is not thoroughly tested (yet) so the results may even be incorrect. Be careful!