liveBook · Manning

0/1 constraint

As explained in Algorithms Every Programmer Should Know

A 0/1 constraint restricts each item decision to either excluding the item or including it once.

Suppose you are choosing cloud instances within a fixed capacity. For each instance, you must either leave it out or take it once. That is the 0/1 constraint: extra capacity does not let you take another copy of the same instance. section 7.1

In a dynamic-programming table, T[i, j] is the best value using the first i items with capacity j. If item i fits, compare skipping it, T[i−1, j], with taking it, vi + T[i−1, j−wi]. Both choices consult the previous row, where item i is not available again. If it does not fit, copy the value above. section 7.1

A choice at capacity 3

The second instance costs 2 and has value 3. Skipping it gives 2; taking it leaves capacity 1, whose previous-row value is 2. Choose 3 + 2 = 5. 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.

Follow the two previous-row lookups to see why taking the instance wins without taking it twice. section 7.1

How Algorithms Every Programmer Should Know covers it

How deep it goes
Works through previous-row table lookups and provides pseudocode and Python implementation.
Examples
Uses cloud-instance choices and a capacity-three table cell to compare exclusion with inclusion.
What it assumes
Starts with zero-item and zero-capacity cases before introducing previous-row lookups.
What you can do after
Build it from scratch with a 2D table that prevents selecting an item more than once.
How it connects
Connects the binary choice to dynamic programming, knapsack optimization, capacity, and table states.

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.