Dynamic Programming Part 5: Approximating Knapsack
Channel: Tech Interviews and Competitive Programming Meetup
Date: 2019-08-20

In this video, I explain how to approximate the solution to the knapsack problem to arbitrary precision using dynamic programming. I show a nice algorithm whose running time depends on the quality of the approximation.

This is Dynamic Programming: Approximating Knapsack, part 5 of a larger series on dynamic programming. It's a recording of a live class that was taught on August 18, 2019 in the Bay Area as part of the Tech Interviews and Competitive Programming Meetup group (https://www.meetup.com/tech-interviews-and-competitive-programming).