Q: Knapsack problem: Given a knapsack with a fixed weight capacity and a set of objects with variable weight and value, what is the maximum value of goods that can be placed in the knapsack, subject to a constraint on the weight?
This is the most famous dynamic programming exercise out there. I did it once in college, but have long since forgotten how. Gulp.
The brute force solution is simple: try every single possible combination of goods.
assert = require('assert');
assert.deepEqual(knapsack([], 10), []);
assert.deepEqual(knapsack([{'value': 5, 'weight': 2}, {'value': 5, 'weight': 2}], 10),
[{'value': 5, 'weight': 2}, {'value': 5, 'weight': 2}]);
assert.deepEqual(knapsack([{'value': 5, 'weight': 2}, {'value': 4, 'weight': 10}], 10),
[{'value': 5, 'weight': 2}]);
assert.deepEqual(knapsack([{'value': 5, 'weight': 10},
{'value': 15, 'weight': 10}], 10),
[{'value': 15, 'weight': 10}]);
evalmachine.<anonymous>:3 assert.deepEqual(knapsack([], 10), []); ^ ReferenceError: knapsack is not defined at evalmachine.<anonymous>:3:8 at ContextifyScript.Script.runInThisContext (vm.js:50:33) at Object.runInThisContext (vm.js:139:38) at run ([eval]:971:15) at onRunRequest ([eval]:798:18) at onMessage ([eval]:758:13) at emitTwo (events.js:126:13) at process.emit (events.js:214:7) at emit (internal/child_process.js:772:12) at _combinedTickCallback (internal/process/next_tick.js:141:11)
function knapsack(items, max_weight):
best_items = []
best_value = 0
for item_combo in items x items: # cross join
if total_weight(item_combo) < max_weight:
if total_value(item_combo) > best_value:
best_items = item_combo
best_weight = total_weight
return best_items
// Helper function for performing a cross join.
var combine = function(a, min) {
var fn = function(n, src, got, all) {
if (n == 0) {
if (got.length > 0) {
all[all.length] = got;
}
return;
}
for (var j = 0; j < src.length; j++) {
fn(n - 1, src.slice(j + 1), got.concat([src[j]]), all);
}
return;
}
var all = [];
for (var i = min; i < a.length; i++) {
fn(i, a, [], all);
}
all.push(a);
return all;
}
function knapsack(goods, max_weight) {
let best_items = [];
let best_value = 0;
if (goods.length == 0) { return []; }
for (let subset of combine(goods, 1)) {
let new_weight = subset.length > 1 ? subset.reduce((a, b) => a.weight + b.weight) : subset[0].weight;
if (new_weight <= max_weight) {
let new_value = subset.length > 1 ? (subset.reduce((a, b) => a.value + b.value)) : subset[0].value;
if (new_value > best_value) {
best_value = new_value;
best_items = subset;
}
}
}
return best_items;
}
If the set $\{a_{i1},\ldots,a_{ik}\}$ does not fit, any superset of this set will not fit either. In other words:
$k(s_1) = F \:\cap\: s_1 \in s_2 \implies k(s_2) = F$
Although we used an iterative solution there is also a recursive solution. In the recursive solution, we try to stick the current item-set in the bag, then try recursively stuffing every one-less subset of the current item-set in the bag, with a base case of no items.
For any particular combination of items (for example, in the simplest case for single items) there is some global weight order $w_{a(i1)} < w_{a(i2)} < \ldots < w_{a(i3)}$. If we attempt to add some $a(ik)$, and it is too heavy to add, all $a(ij)$ where $j > k$ will also be too heavy.
The global weight order for sets of size $n$ may be easily derived from knowing the global weight order of sets of size $n-1$.
If we know the weight and value of set $s1$, and set $s2$ adds a single item $k$ to $s1$, then we have the following recurrence relationships:
$w_{s2} = w_{s1} + w_k$
$v_{s2} = v_{s2} + v_k$
From P1 we see that if we construct a loop through item-sets whose first order sort is the set size, we may eliminate many possible non-comformant combinations from consideration by eliminating smaller non-conformant subsets earlier in the loop.
From P3,P4 we see that we can easily construct a loop whose second order sort is the total weight of the set (e.g. each pass would be an in-order list of sets of the same size by weight ascending), which would further allow us to eliminate all remaining sets to be iterated over as soon as the first set in the list fails the weight test.
From P5 we see that if we memoize previous weight calculations, we may calculate the new weight and value using two comparison operations instead of very many of them.
function knapsack(items, max_weight):
itemsets = sorted_by_weight(items)
max_value = 0
max_itemset = []
while len(itemsets) > 0:
items_i = 0
while items_i < len(itemsets):
if total_weight(itemsets[items_i]) <= max_weight:
current_value = total_value(itemsets[items_i])
if current_value > max_value:
max_itemset = itemsets[items_i]
max_value = current_value
items_i += 1
if len(itemsets) <= items_i:
break
else:
itemsets = itemsets[:items_i]
break
itemsets = sorted_by_weight({itemsets cross join individual items})
return max_itemset
Note that this psuedocode is missing an exit condition for when the entire current sublist is retained, and that it doesn't implement P5 memoization. The former was a mistake and the latter an optimization that didn't require significant code refactoring, so I did it later.
We first need to implement a test an ordered upsize-by-one algorithm, which is a non-trivial component of the algorithm above.
function _append_itemset(itemsets, items) {
let out = [];
itemsets.forEach(itemset => {
items.forEach(item => {
if (!itemset.includes(item)) {
out.push(itemset.concat([item]));
}
});
});
return out;
}
assert.deepEqual(_append_itemset([], []), []);
assert.deepEqual(_append_itemset([[1]], [1, 2, 3]), [[1, 2], [1, 3]]); // Needs to preserve order!
assert.deepEqual(_append_itemset([[1]], [1, 2, 3]), [[1, 2], [1, 3]]);
Now we implement the primary function.
function knapsack(items, max_weight) {
if (items.length == 0) { return []; }
let itemsets = items.sort((a, b) => a.weight < b.weight).map(v => [v]);
let max_value = 0;
let max_itemset = [];
while (itemsets.length > 0) {
// console.log("TOP OF THE LOOP");
// console.log(itemsets.length);
// console.log(itemsets);
let items_i = 0;
while (items_i < itemsets.length) {
let curr_set = itemsets[items_i];
// console.log("SUBLOOP");
// console.log(items_i);
// console.log(curr_set);
let total_weight = curr_set.length > 1 ?
curr_set.reduce((a, b) => a.weight + b.weight) :
curr_set[0].weight;
// console.log(total_weight);
if (total_weight <= max_weight) {
let current_value = curr_set.length > 1 ?
curr_set.reduce((a, b) => a.value + b.value) :
curr_set[0].value;
if (current_value > max_value) {
max_itemset = curr_set;
max_value = current_value;
}
items_i += 1;
}
else {
// console.log("BROKE OUT BY SHORTENING THE LIST");
itemsets = itemsets.slice(0, items_i);
break;
}
if (itemsets.length <= items_i) {
// console.log("BROKE OUT BY EXHAUSTING THE LIST");
break;
}
}
itemsets = _append_itemset(itemsets, items);
}
return max_itemset;
}
We'll perform another optimization now: memoization. Here's the psuedocode for this second round:
function knapsack(items, max_weight):
itemsets = sorted_by_weight(items)
max_value = 0
max_itemset = []
memo = {}
while len(itemsets) > 0:
items_i = 0
while items_i < len(itemsets):
if total_weight(itemsets[items_i]) <= max_weight:
current_value = total_value(itemsets[items_i])
if current_value > max_value:
max_itemset = itemsets[items_i]
max_value = current_value
items_i += 1
if len(itemsets) <= items_i:
break
else:
itemsets = itemsets[:items_i]
break
if items_i >= len(itemsets):
break
itemsets = _append_itemset(itemsets, items, memo)
return max_itemset
function total_weight(items, memo):
if items.length = 1:
key = Set(items)
memo[key] = items[0].weight
return memo[key]
else:
key = Set(items[:-1])
next_key = Set(items)
memo[next_key] = memo[key] + items[-1].weight
return memo[next_key]
function total_value(items, memo):
if items.length = 1:
key = Set(items)
memo[key] = items[0].value
return memo[key]
else:
key = Set(items[:-1])
next_key = Set(items)
memo[next_key] = memo[key] + items[-1].value
return memo[next_key]
And now the algorithm. The memoization is separable to a separate function, which we'll define, test the correctness of, and then implement the algorithm itself.
function _total_prop(items, memo, accessor) {
if (items.length === 1) {
key = JSON.stringify(Array.from(new Set(items)));
memo[key] = accessor(items[0]);
return memo[key];
} else {
key = JSON.stringify(Array.from(new Set(items.slice(0, items.length - 1))));
next_key = JSON.stringify(Array.from(new Set(items)));
memo[next_key] = memo[key] + accessor(items[items.length - 1]);
return memo[next_key];
}
}
let fake_memo = {};
let fae_key = {};
assert.equal(_total_prop([{value: 1, weight: 1}], [], v => v.weight), 1)
fake_memo = {};
fake_key = JSON.stringify(Array.from(new Set([{value: 1, weight: 1}])));
fake_memo[fake_key] = 1;
assert.equal(_total_prop([{value: 1, weight: 1}, {value: 2, weight: 2}], fake_memo, v => v.weight), 3)
fake_memo = {};
fake_key = JSON.stringify(Array.from(new Set([{value: 1, weight: 1}, {value: 2, weight: 2}])));
fake_memo[fake_key] = 3;
assert.equal(_total_prop([{value: 1, weight: 1}, {value: 2, weight: 2}, {value: 3, weight: 3}],
fake_memo, v => v.weight), 6)
function knapsack(items, max_weight) {
if (items.length == 0) { return []; }
let itemsets = items.sort((a, b) => a.weight < b.weight).map(v => [v]);
// console.log(itemsets);
let max_value = 0;
let max_itemset = [];
let memo = {};
while (itemsets.length > 0) {
let items_i = 0;
while (items_i < itemsets.length) {
let curr_set = itemsets[items_i];
let total_weight = _total_prop(curr_set, memo, v => v.weight);
if (total_weight <= max_weight) {
// let current_value = _total_prop(curr_set, memo, v => v.value);
let current_value = curr_set.length > 1 ?
curr_set.reduce((a, b) => a.value + b.value) :
curr_set[0].value;
if (current_value > max_value) {
max_itemset = curr_set;
max_value = current_value;
}
items_i += 1;
}
else {
itemsets = itemsets.slice(0, items_i);
break;
}
if (itemsets.length <= items_i) {
break;
}
}
itemsets = _append_itemset(itemsets, items);
}
return max_itemset;
}
knapsack([{'value': 5, 'weight': 2}, {'value': 4, 'weight': 10}], 10);
[ { value: 5, weight: 2 } ]
fake_key = new Set([{v: 1, w: 2}])
fake_memo = new Map();
fake_memo[fake_key] = 2;
fake_key = new Set([{v: 5, w: 5}])
fake_memo[fake_key] = 5;
5
TODO: this mostly works, except for an object-key issue...https://stackoverflow.com/questions/51846362/does-javascript-allow-set-keys-for-objects-fields