How to Solve the Knapsack Problem using Dynamic Programming

You have a bag with a fixed weight capacity and a list of items each with a weight and a value. You must choose items to maximize total value without exceeding the weight capacity. You either take an item completely or leave it entirely.

The subproblem is: what is the maximum value achievable using only the first i items with a bag capacity of w. Solving this for every combination of i and w gives you the answer to the full problem.

Create a two dimensional table with rows equal to the number of items plus one and columns equal to the maximum capacity plus one. The extra row and column represent the base case of zero items or zero capacity, and all those cells are filled with zero.

Go through each item one by one. For each item, go through every possible capacity from zero up to the maximum. At each cell, make a decision based on whether you can fit the current item.

If the current item's weight is greater than the current capacity, you cannot take it. Copy the value from the cell directly above. If you can fit the item, compare two choices: skip the item and take the value above, or take the item and add its value to the best value achievable with the remaining capacity from the previous row. Store whichever is greater.

After filling the entire table, the answer is in the very last cell at the bottom right corner. It represents the maximum value achievable using all items with the full capacity.

To find which items were chosen, start from the last cell and move upward. If the value differs from the cell directly above, that item was included. Subtract its weight from the capacity and move to the previous row. If the value matches the cell above, the item was skipped. Continue until you reach row zero.