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

Each item may be chosen once, so the DP update direction is part of correctness. Updating capacities in descending order ensures best[c-weight] still belongs to the previous item layer. Ascending order lets the same item feed its own newly written state and changes the problem into unbounded knapsack.

Preventing a file from being counted twice

With files (size=2, score=3) and (size=3, score=4), a budget of five can earn seven. In a one-row table, process capacities downward when considering each file. Then the smaller source capacity still describes earlier files. Processing upward would let the size-two file reuse its own update and pretend two copies were available.

// One item has size 2 and score 3; it may be selected only once.
const Int weight = 2, value = 3, limit = 4;
std::vector<Int> best(limit + 1, 0);
for (Int capacity = limit; capacity >= weight; --capacity) {
    best[capacity] = std::max(best[capacity], best[capacity - weight] + value);
}
std::cout << best[4] << '\n'; // 3, rather than the invalid two-copy score 6.

A budget-sized table has a limit

An empty selection is valid; initialize all capacities to zero rather than to a negative sentinel. Duplicate item tuples are separate selectable objects. Positive weights avoid a zero-width dependency, and nonnegative values make unused capacity harmless. Enumerating subsets is a transparent prototype and gives an independent small-input oracle. The final single-row DP costs O(nC) time/O(C) space. Use signed loop cursors to avoid underflow at capacity zero.

For n files and integer capacity C, the value table takes O(nC) time and O(C) auxiliary space. C is a numeric bound, so this is pseudo-polynomial. Returning only the maximum score needs less state than reconstructing the chosen files; fractional files and reusable items are different models.

Use the supplied Int, Vec, and Opt aliases. Numeric arithmetic fits signed long long; absence uses std::nullopt, and documented invalid inputs throw std::invalid_argument. Keep caller-owned containers unchanged.

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