Question

Write the dynamic programming algorithm for the 0 - 1 Knapsack Problem.

Short answer

The maximum value that can be achieved with n items and weight W is stored at knapsackTable[n][W]. Also, moving from knapsackTable[n][W] towards knapsackTable[0][0] helps to retrieve the items that are included in the knapsack and that collectively gives the maximum value.

Step-by-step solution

Problem Formulation

Given weights[] array that represents weights of n items and value[] array for the values of the corresponding items, and an integer W representing the maximum weight the knapsack can hold, the task is to find the maximum value that can be achieved. An item can be selected or not selected (0-1 property) creating a 'dynamic' programming problem.

Initialize Dynamic Programming Table

Create a 2D array knapsackTable[n+1][W+1], where n is the number of items and W is the maximum weight the knapsack can hold. Initialize all elements of the first row and first column to zero. This represents the case where we have 0 items or the maximum weight the knapsack can hold is 0.

Fill the DP table

For each item (starting from 1 to n), iterate through each weight (from 1 to W). For each cell knapsackTable[i][j], check if weights[i-1] (weight of the current item) is smaller than or equal to j (current weight capacity). If it is, then the maximum value at this cell can be achieved either by including the current item (values[i-1] + knapsackTable[i-1][j-weights[i-1]]) or by excluding the current item (knapsackTable[i-1][j]). The maximum value is set as value of knapsackTable[i][j]. If the weight of current item is greater than the j, then the item cannot be included and therefore, value at knapsackTable[i-1][j] is carried down to knapsackTable[i][j].

Find the Maximum Value

The maximum value that can be achieved with n items and weight W is stored in knapsackTable[n][W]. So the maximum value that can be achieved is knapsackTable[n][W]

Retrieving the Items

To get the items that are included in the knapsack, start from knapsackTable[n][W] and move towards knapsackTable[0][0]. If value at knapsackTable[i][j] is equal to knapsackTable[i-1][j], this means current item is not included. Hence, decrease the 'i' counter (Go to the previous item). Otherwise, if the value comes from including the item, decrease the 'i' counter (Go to the previous item) and decrease 'j' by weights[i] (Move to the column representing the remaining weight after including the current item).