Skip to content

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.

Start Exercises Lab Quiz Downloads

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.

More apps in the lab

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

    The chapters

  • 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)

    The chapters

  • Lot sizing problems


    Part 3 · Chapters 10–11

    Uncapacitated lot sizing (ULS) · Capacitated lot sizing (CLS)

    The chapters

  • Miscellaneous problems


    Part 4 · Chapters 12–13

    Coin change (CCP) · Rod cutting (RCP)

    The chapters

  • Self-assessment


    Mock exam

    A new mock exam at every start: 13 questions, 33 points, with the solutions and links to the notes.

    Test yourself

  • Lab


    Interactive apps

    The DP tables filling step by step, on the reference instances or on your own.

    The apps

Don't miss

  • Exercises with solutions


    Exercises for every chapter, each with its worked solution that opens with a click.

    The exercises

  • 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.

    Test yourself

  • Interactive lab


    Apps running in the browser: move the parameters and watch the ideas of the course at work, one step at a time.

    The lab

  • Lecture notes in PDF


    Lecture notes, exercise books and slides in PDF, with the same numbering as the website.

    Downloads

  • Full index


    All the chapters with their sections on one page, and how each chapter is organized.

    The index


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.

  • Mathematical Analysis 1

    real numbers, functions, limits, derivatives and series, with interactive graphs

  • Linear Algebra

    vectors, matrices, determinants, linear systems and eigenvalues, with the computation lab

  • Algorithms

    number representation, pseudo-code, sorting and searching, analysis and recursive algorithms

  • Linear Programming

    polyhedra, the simplex algorithm, duality and the dual simplex, with the interactive lab

  • Integer Linear Programming

    LP relaxation, valid inequalities, cutting planes, branch-and-bound and branch-and-cut

  • Convex Optimization

    convex sets and functions, convex optimization problems, with interactive graphs

  • Network Optimization

    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

  • Heuristic Algorithms

    constructive heuristics, local search, metaheuristics and MIP heuristics for combinatorial optimization problems

  • Approximation Algorithms

    performance guarantees, approximation schemes and limits of approximation for combinatorial problems

  • LP Modelling

    linear programming models of managerial problems, solved with Python and Gurobi

  • NLP Modelling

    nonlinear programming models, from portfolios to machine learning, with Python and Gurobi

  • MIP Modelling

    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.