liveBook · Manning

Capacity

As explained in Algorithms Every Programmer Should Know

Capacity is the maximum total resource amount that a selected collection of items may consume.

Imagine choosing cloud-service instances for a server with a budget of eight credits. Each instance costs credits and adds processing throughput. Capacity is the hard ceiling: the selected instances may cost eight credits in total, but not nine. The goal is to get the most throughput without crossing that ceiling. section 7.1

A dynamic programming table considers every smaller capacity from zero through the full limit W. Cell T[i, j] holds the best value obtainable from the first i items while using no more than j capacity. The zero-item row and zero-capacity column contain zero. These smaller budgets let the algorithm reuse answers instead of reconsidering every selection from scratch. section 7.1 section 7.4

For each item and capacity, ask whether the item fits:

  • If its weight exceeds the current capacity, skip it and copy the value from the row above. section 7.1
  • If it fits, compare skipping it with taking its value plus the previous row’s answer for the capacity left over. Using the previous row prevents taking the same item twice. section 7.1

A choice at capacity eight

Suppose the last instance costs five credits and adds six units of value. At capacity eight, skipping it gives 10. Taking it leaves capacity three, whose earlier best value is five; 6 + 5 = 11. The better answer is 11, with total cost still within eight credits. section 7.1

Figure 7.3 Visualization of the math used to evaluate cell T[2, 3] (circled in green) on the second row (w2 = 2, v2 = 3). The algorithm resolves a binary choice by executing a maximum value comparison between two paths. The exclusion path inherits the value directly above (T[1, 3] = 2). The active inclusion path accepts the new instance's throughput value (v2 = 3, highlighted in the red solid box) and subtracts its weight from the current capacity (3 - 2 = 1), forcing a pointer lookup to the previous row at column 1 (T[1, 1] = 2, highlighted by the red dotted circle). The combined value of 5 outperforms the exclusion path, updating the cell state.

The marked cells show why taking an item means looking up its remaining capacity in the previous row, then comparing that result with skipping it. section 7.1

Capacity also determines the table’s size. With n items and a numeric limit W, the standard table uses (n + 1) × (W + 1) cells and takes O(nW) time and space. Eight credits makes a small table; an enormous numeric limit can make the same approach impractical even with only four items. section 7.3

How Algorithms Every Programmer Should Know covers it

How deep it goes
Works through capacity-indexed table states, boundary values, and inclusion-or-exclusion lookups, then identifies limits when the numeric capacity grows.
Examples
Uses an eight-credit cloud-instance budget, a capacity-indexed matrix, and a final choice between values 10 and 11.
What it assumes
Introduces item weights, values, and the capacity limit before building the dynamic programming table.
What you can do after
Build it from scratch using a capacity-indexed 0/1 knapsack table to choose the highest-value combination that fits.
How it connects
Connects capacity to 0/1 knapsack, dynamic programming, overlapping subproblems, and pseudo-polynomial complexity.

Also explained in

Compare how 8 books explain capacity →

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Algorithms Every Programmer Should Know. The section links point to the parts of the book it draws on.