Reducibility
Glossary Contents
← Ch XVII
Chapter XVIII Knapsack
Ch XIX →
  1. 52 — The knapsack
  2. 53 — DP in C#
  3. 54 — Capital budgeting and ad slots
54

Capital budgeting and ad slots

Every CFO who has ever asked "which projects do we fund?" with a fixed budget has solved a knapsack.

Same setting as 0-1 IP, but the simple form: each candidate has a cost and an expected return; total budget is capped; maximize total return. Knapsack DPs are embedded in real-time ad serving (each ad has a CPM and uses a quota of the user's session — pick the highest-value compatible set), in containerization (ECR / Cloud Run schedulers fitting Pod requests into nodes are running a vector knapsack), and in cargo loading (max value of cargo into a vessel within deadweight). Tax-loss harvesting is a knapsack: each lot has a "loss" and a "drift cost"; maximize loss subject to a tracking-error budget. Wealthfront and Betterment both run this nightly.

In plain terms

A streaming service has 10 seconds of ad time and a list of ads, each paying differently and taking different lengths. Pick the most lucrative combination that fits in the slot. That's knapsack, and it runs millions of times per second.

Scan to come back to page 54

End of Chapter XVIII
Chapter XIX Job Sequencing →
← 53 DP in C#
3/3 · 54/63
55 Deadlines on a single machine →