0/1 knapsack

A field tablet has a fixed download budget before it goes offline. Each manual has an integer size and a usefulness score. A manual is either downloaded once or omitted; downloading it twice doesn't double its value.

The largest score or best score-per-megabyte can be tempting, but an awkward leftover capacity can make either choice lose. The 0/1 knapsack model compares taking and skipping each file while respecting the remaining budget.

Choosing files for an offline tablet

0/1 knapsack chooses a subset of items whose total weight fits capacity and whose total value is largest. Each item may be used once. Duplicate item records still describe separate choices; deduplicating them would change the problem.

Enumerating all subsets is a transparent prototype. Dynamic programming instead reuses the best value for each capacity after considering a prefix of items.

Preventing a file from being counted twice

A two-row recurrence decides whether the current item is excluded or included using a value from the previous item layer. One row is enough if capacities are updated downward. Then best[c-weight] still belongs to the previous layer. An upward pass reuses the same item's newly written values and changes the problem into unbounded knapsack.

With one item of weight 2 and value 3 and capacity 4, the answer is 3, not 6. Initializing every capacity to zero represents choosing nothing and allows unused capacity. A negative sentinel is unnecessary because the empty selection is always valid.

Validate capacity and every item before indexing or allocating a table. Positive weights prevent zero-width dependencies; nonnegative values keep the empty selection a legitimate lower bound. Arrays of [weight, value] pairs are input records, so copying only the outer array does not permit mutating their inner contents.

const best = [0, 0, 3, 3, 3]; // after considering one [2, 3] item
console.log(best[4]); // 3: item identity prevents choosing it twice
const item = [2, 3];
const [weight, value] = item;
console.log(weight, value); // 2 3

A budget-sized table has a limit

Subset enumeration costs O(2^n) choices. The final DP takes O(nC) time and O(C) auxiliary space for capacity C. That is pseudo-polynomial in the numeric capacity, so very large capacities may need a different strategy. This model fits indivisible independent items; fractional selection or unlimited copies requires a different algorithm.

If a manual depends on downloading another file first, include that dependency in the model before trusting this independent-item table.