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

Choose a subset under a capacity limit with each input item available once. Duplicate item records represent two separate opportunities, not unlimited reuse of one item.

Enumerating subsets gives a baseline, while choosing by value/weight ratio is not generally correct for indivisible items. Compressing DP to one array saves space only if updates read the previous-item state.

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.

In a one-dimensional 0/1 table, capacities must be updated in descending order. Ascending updates would read the same item's new state and allow reuse. Each duplicate record is still a separate item. Prototype enumerates subsets; final O(nC) time and O(C) auxiliary space.

Ascending updates can reuse the current item. This deliberately small counterexample shows the dependency error:

import java.util.*;

class Example {
    public static void main(String[] args) {
        long[] unsafe = new long[5];
        int weight = 2;
        long value = 3;
        for (int capacity = weight; capacity < unsafe.length; capacity++) {
            unsafe[capacity] = Math.max(unsafe[capacity], unsafe[capacity - weight] + value);
        }
        assert unsafe[4] == 6; // one item was incorrectly used twice
    }
}

The result violates the 0/1 contract for one item. A dependency-safe final implementation must prevent a state updated by the current item from being read again for that item. This snippet is a failure demonstration, not a valid knapsack solution.

A budget-sized table has a limit

0/1 resource selection is useful when work units, features, or assets cannot be divided or reused. Changing availability to unlimited copies changes the dependency direction and the underlying problem.

Each item has weight > 0 and value >= 0; capacity must be >= 0, otherwise IllegalArgumentException. Return the maximum total value with each item used at most once. Empty selection and unused capacity are allowed.

Numeric arithmetic uses long; indices use int. Inputs follow the declared types and contain no null elements unless the API permits them. Preserve caller-owned collections, including on failure, and use IllegalArgumentException for the documented invalid arguments.

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