Knapsack Problem (Dynamic Programming)

How the Knapsack Problem Works

The Knapsack problem is a problem in combinatorial optimization: Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.

The algorithm:

1. Create a table where rows represent items and columns represent weights from 0 to the knapsack capacity
2. Fill the table using bottom-up dynamic programming
3. For each cell, decide whether to include the current item or not, based on which choice maximizes value
4. The value in the bottom-right cell is the maximum achievable value
5. Backtrack through the table to determine which items were selected

This dynamic programming approach solves the problem in O(nW) time complexity, where n is the number of items and W is the knapsack capacity.

function knapsack(W, wt, val, n):
    K = 2D array of size (n+1) x (W+1)
    
    for i from 0 to n:
        for w from 0 to W:
            if i == 0 or w == 0:
                K[i][w] = 0
            elif wt[i-1] <= w:
                K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]], K[i-1][w])
            else:
                K[i][w] = K[i-1][w]
            visualize(K, i, w, wt, val)
    
    return K[n][W]

function visualize(K, i, w, wt, val):
    // Update UI to show:
    // 1. The current state of the K array
    // 2. Highlight the current cell being calculated
    // 3. Show the weight and value of the current item
    // 4. Indicate which case of the algorithm is being applied