Dynamic Programming¶
A course of the Operations Research and Mathematics series · all the courses
Teaching material conceived and developed by Fabio Furini, associate professor at DIAG, Sapienza University of Rome.
The course lecture notes, online: the principles of dynamic programming and DP algorithms for knapsack problems (0/1, unbounded, bounded, subset sum, multiple-choice, multidimensional, with setups, multiple knapsack), for uncapacitated and capacitated lot sizing, coin change and rod cutting; with recurrences, pseudo-code, complexity, tables worked out step by step, exercises with solutions and interactive apps.
Prerequisites: Combinatorial Optimization Problems for the problems and Algorithms for pseudo-code, recursion and the analysis of algorithms.
Try it now¶
The dynamic programming table for the 0/1 knapsack, already filled: each cell is the best profit with the first j items and capacity k, and the green path reconstructs the solution. Press «Run» to watch it fill one cell at a time.
The parts of the course¶
The same entries as the menu: each card gives its part and its chapters in the lecture notes.
-
Principles
Part 1 · Chapter 1
Principles
-
Knapsack problems
Part 2 · Chapters 2–9
0/1 knapsack (KP) · Unbounded knapsack (UKP) · Bounded knapsack (BKP) · Subset sum (SSP) · Multiple-choice knapsack (MCKP) · Multidimensional knapsack (MDKP) · Knapsack with setups (KPS) · Multiple knapsack (MKP)
-
Lot sizing problems
Part 3 · Chapters 10–11
Uncapacitated lot sizing (ULS) · Capacitated lot sizing (CLS)
-
Miscellaneous problems
Part 4 · Chapters 12–13
Coin change (CCP) · Rod cutting (RCP)
-
Self-assessment
Mock exam
A new mock exam at every start: 13 questions, 33 points, with the solutions and links to the notes.
-
Lab
Interactive apps
The DP tables filling step by step, on the reference instances or on your own.
Don't miss¶
-
Exercises with solutions
Exercises for every chapter, each with its worked solution that opens with a click.
-
Self-assessment quiz
A new mock exam at every start: 13 questions, 33 points, with the solution and the link to the notes. Downloads also has the full question bank.
-
Interactive lab
Apps running in the browser: move the parameters and watch the ideas of the course at work, one step at a time.
-
Lecture notes in PDF
Lecture notes, exercise books and slides in PDF, with the same numbering as the website.
-
Full index
All the chapters with their sections on one page, and how each chapter is organized.
The series¶
All the courses of the series are built the same way: lecture notes online and in PDF, exercises with solutions, an interactive lab and self-assessment quizzes.
-
real numbers, functions, limits, derivatives and series, with interactive graphs
-
vectors, matrices, determinants, linear systems and eigenvalues, with the computation lab
-
number representation, pseudo-code, sorting and searching, analysis and recursive algorithms
-
polyhedra, the simplex algorithm, duality and the dual simplex, with the interactive lab
-
LP relaxation, valid inequalities, cutting planes, branch-and-bound and branch-and-cut
-
convex sets and functions, convex optimization problems, with interactive graphs
-
graphs, spanning trees, shortest paths, network flows, the network simplex and project management
-
Combinatorial Optimization Problems
knapsack, bin packing, coloring, TSP, scheduling and lot sizing: the problems, their formulations and ad hoc algorithms
-
Dynamic Programming · this course
principles and DP algorithms for knapsack, lot sizing, coin change and rod cutting
-
constructive heuristics, local search, metaheuristics and MIP heuristics for combinatorial optimization problems
-
performance guarantees, approximation schemes and limits of approximation for combinatorial problems
-
linear programming models of managerial problems, solved with Python and Gurobi
-
nonlinear programming models, from portfolios to machine learning, with Python and Gurobi
-
integer linear programming models, from the formulation to the solution with solvers
Teaching material by Fabio Furini — DIAG, Sapienza University of Rome.
This website is also available in Italian.