11 Dynamic Programming and Sequencing
Many decisions are taken in stages: how much to produce this month and next, how many salesmen to send to each region in turn, which item to put in the knapsack next. Dynamic programming, developed by Bellman in the 1950s, solves such problems by working backwards from the last stage, using one simple principle: whatever the earlier decisions, the remaining ones must be optimal for the situation they left. It turns an exponential search into a sequence of small optimisations, and it handles non-linear returns and integer decisions with no extra effort. The second half of the section treats sequencing, the ordering of jobs on machines, where simple rules proved by exchange arguments give optimal schedules.
11.2 The knapsack problem
11.3 Allocating a resource
11.4 Sequencing jobs
11.5 Dynamic programming in software
11.6 Practice Problems
Questions on this section
Stuck on something here? Ask below and it stays attached to this topic.