? Check out my Dynamic Programming course (founders edition available):
https://techwithnikola.com/course/dynamic-programming#founders
Six modules are available now, with animated explanations, coding exercises, and Python solutions. Your purchase includes lifetime access and the remaining modules as I release them.
In this video, we start with an example where choosing the best value per kilo gives the wrong answer. Then we choose a state, derive the recurrence, and write Python code for both versions.
Using the same backpack and items throughout, we’ll see why the remaining capacity tells us enough when copies are unlimited, and why we also need to track which items are available when we only have one of each. We’ll finish by comparing the time and space complexity of both solutions.
The course also covers how to reduce the memory used by the 0/1 solution, including why the order of updates matters.
Some familiarity with basic dynamic programming will help you follow along.
#DynamicProgramming #KnapsackProblem #Algorithms
Chapters
0:00 Why greedy doesn't always work
1:01 Unlimited knapsack: state, recurrence, and code
4:05 0/1 knapsack: allowing each item only once
8:32 Time and space complexity