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 selection differs from unlimited reuse. A one-dimensional table can hold the best value for each capacity, but update direction determines whether the current item can feed itself. The state must represent a decision prefix, not an unbounded choice pool.

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.

items, limit := [][2]int{{2, 3}, {3, 4}}, 5
best := make([]int, limit+1)
for _, item := range items {
	weight, value := item[0], item[1]
	for capacity := limit; capacity >= weight; capacity-- {
		candidate := best[capacity-weight] + value
		if candidate > best[capacity] {
			best[capacity] = candidate
		}
	}
}
fmt.Println(best[limit]) // 7; descending updates prevent reusing an item.

A budget-sized table has a limit

A heavier item with a larger value may still lose to two lighter items. Capacity means an upper bound, so unused space is legal. Integer capacity gives pseudo-polynomial O(nC) work; enormous capacities call for another representation or approximation. Tests that contain a single item and twice its weight catch accidental unbounded reuse.

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.

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