Dynamic programming¶
Part 3 of the course, volume 3 of the lecture notes: chapters 16–28.
The principles of dynamic programming and DP algorithms for knapsack problems, lot sizing, coin change and rod cutting: recurrences, pseudocode, complexity and worked tables.
Lecture notes (PDF) Exercises (PDF)
-
16. Principles of dynamic programming
Divide, conquer and combine · Problem properties required by DP algorithms · Steps for designing a DP algorithm · The DP algorithms of this module
Knapsack problems¶
-
17. DP for the 0/1 knapsack problem
Instances and feasible solutions · A first DP algorithm · A second DP algorithm
-
18. DP for the unbounded knapsack problem
Instances and feasible solutions · A first DP algorithm · A second DP algorithm
-
19. DP for the bounded knapsack problem
Instances and feasible solutions · A DP algorithm
-
20. DP for the subset sum problem
A DP algorithm
-
21. DP for the multiple-choice knapsack problem
A DP algorithm
-
22. DP for the multidimensional knapsack problem
A DP algorithm
-
23. DP for the knapsack problem with setups
A DP algorithm
-
24. DP for the multiple knapsack problem
A DP algorithm
Lot sizing problems¶
-
25. DP for the uncapacitated lot sizing problem
Notation, model and feasible solutions · A DP algorithm for the ULS
-
26. DP for the capacitated lot sizing problem
Notation, model and feasible solutions · A DP algorithm for the CLS
Miscellaneous problems¶
-
27. DP for the coin change problem
Instances and feasible solutions · A DP algorithm
-
28. DP for the rod cutting problem
Instances and feasible solutions · A first DP algorithm · A second DP algorithm