[Verse 1] Got a backpack and some items, need to maximize my gain Each item got a value and a weight that's plain Zero-one means take it once or leave it on the shelf Dynamic programming gonna help me help myself Build a table, rows for items, columns for the weight Bottom up approach, let me demonstrate If the item weighs too much for current capacity Skip it, take the value from the row above, you see [Chorus] Knapsack problem, optimize the load Take or leave it, that's the zero-one code Unbounded version, take as many as you need Dynamic table fills up with the optimal feed Max value, check the weight Fill the table, don't be late Knapsack wisdom, algorithmic state [Verse 2] Unbounded knapsack got a different kind of flow Take the same item multiple times, watch the value grow For each weight from one up to capacity Check every item that could fit naturally Take the max of leaving space or adding one more in Previous best or current item plus what's left to win Recurrence relation keeps the logic tight and clean Most efficient packing that you've ever seen [Chorus] Knapsack problem, optimize the load Take or leave it, that's the zero-one code Unbounded version, take as many as you need Dynamic table fills up with the optimal feed Max value, check the weight Fill the table, don't be late Knapsack wisdom, algorithmic state [Bridge] Time complexity, oh en times double-u Space can be reduced if you know what to do Greedy won't work here, need the DP way Overlapping subproblems save the day Memoization or tabulation method Both will get you to the solution you intended [Verse 3] Backtrack through the table if you need to see the items Trace the optimal choices, see how the algorithm fights them Start from bottom right, work your way back up If values differ from the row above, fill up your cup That item made the cut, add it to your list Zero-one or unbounded, neither can be missed Real world applications from resource allocation To cutting stock problems across every nation [Chorus] Knapsack problem, optimize the load Take or leave it, that's the zero-one code Unbounded version, take as many as you need Dynamic table fills up with the optimal feed Max value, check the weight Fill the table, don't be late Knapsack wisdom, algorithmic state [Outro] Pack it up smart, with the algorithm's art Dynamic programming, playing the part Zero-one or unlimited, both serve their role Knapsack mastery is the ultimate goal
← Longest increasing subsequence | Matrix chain multiplication →