0/1 Knapsack Problem: Interactive Dynamic Programming Tutorial

Description

The 0/1 Knapsack problem is a classic optimization problem where given a set of items, each with a weight and value, we need to determine which items 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 term "0/1" indicates that we must either take an item completely (1) or leave it (0).

History

The Knapsack problem was first studied in the early 20th century and has since become one of the most researched problems in combinatorial optimization. Its name comes from the problem faced by someone who is constrained by a fixed-size knapsack and must fill it with the most valuable items. The problem has found applications in resource allocation, cargo loading, cutting stock problems, and even in cryptography. The dynamic programming solution was developed in the 1950s and remains the most practical approach for moderate-sized instances.

How It Works

Initialize DP Table:
- Create a table of size (n+1) × (W+1)
- n is number of items, W is capacity
- Initialize first row and column with zeros
Fill DP Table:
- For each item i and weight w
- If item can fit (weight ≤ w), choose maximum of:
- - Including item: value[i] + dp[i-1][w-weight[i]]
- - Excluding item: dp[i-1][w]
Trace Solution:
- Start from bottom-right cell
- Compare with cell above to determine if item was included
- Move to previous state based on decision

Visualization

Speed:

Click Start to begin visualization

Implementation


def knapsack(values, weights, capacity):
    n = len(values)
    dp = [[0 for _ in range(capacity + 1)] for _ in range(n + 1)]
    
    # Fill dp table
    for i in range(1, n + 1):
        for w in range(capacity + 1):
            if weights[i-1] <= w:
                dp[i][w] = max(
                    values[i-1] + dp[i-1][w-weights[i-1]],  # Include item
                    dp[i-1][w]                              # Exclude item
                )
            else:
                dp[i][w] = dp[i-1][w]  # Can't include item
    
    # Find selected items
    selected = []
    i, w = n, capacity
    while i > 0 and w > 0:
        if dp[i][w] != dp[i-1][w]:
            selected.append(i-1)
            w -= weights[i-1]
        i -= 1
    
    return dp[n][capacity], selected[::-1]

# Example usage
if __name__ == "__main__":
    values = [3, 4, 5, 6]
    weights = [2, 3, 4, 5]
    capacity = 10
    
    max_value, selected_items = knapsack(values, weights, capacity)
    print(f"Maximum value: {max_value}")
    print(f"Selected items: {selected_items}")


#include <vector>
#include <iostream>

struct KnapsackResult {
    int maxValue;
    std::vector selectedItems;
};

KnapsackResult knapsack(const std::vector& values, 
                       const std::vector& weights, 
                       int capacity) {
    int n = values.size();
    std::vector> dp(n + 1, 
        std::vector(capacity + 1, 0));
    
    // Fill dp table
    for(int i = 1; i <= n; i++) {
        for(int w = 0; w <= capacity; w++) {
            if(weights[i-1] <= w) {
                dp[i][w] = std::max(
                    values[i-1] + dp[i-1][w-weights[i-1]],
                    dp[i-1][w]
                );
            } else {
                dp[i][w] = dp[i-1][w];
            }
        }
    }
    
    // Find selected items
    std::vector selected;
    int i = n, w = capacity;
    while(i > 0 && w > 0) {
        if(dp[i][w] != dp[i-1][w]) {
            selected.push_back(i-1);
            w -= weights[i-1];
        }
        i--;
    }
    
    // Reverse to get items in original order
    std::reverse(selected.begin(), selected.end());
    
    return {dp[n][capacity], selected};
}

int main() {
    std::vector values = {3, 4, 5, 6};
    std::vector weights = {2, 3, 4, 5};
    int capacity = 10;
    
    auto result = knapsack(values, weights, capacity);
    
    std::cout << "Maximum value: " << result.maxValue << std::endl;
    std::cout << "Selected items: ";
    for(int item : result.selectedItems) {
        std::cout << item << " ";
    }
    std::cout << std::endl;
    
    return 0;
}


using System;
using System.Collections.Generic;

public class KnapsackSolver {
    public class KnapsackResult {
        public int MaxValue { get; set; }
        public List<int> SelectedItems { get; set; }
    }
    
    public static KnapsackResult Solve(int[] values, int[] weights, int capacity) {
        int n = values.Length;
        int[,] dp = new int[n + 1, capacity + 1];
        
        // Fill dp table
        for(int i = 1; i <= n; i++) {
            for(int w = 0; w <= capacity; w++) {
                if(weights[i-1] <= w) {
                    dp[i,w] = Math.Max(
                        values[i-1] + dp[i-1,w-weights[i-1]],
                        dp[i-1,w]
                    );
                } else {
                    dp[i,w] = dp[i-1,w];
                }
            }
        }
        
        // Find selected items
        List<int> selected = new List<int>();
        int currentWeight = capacity;
        for(int i = n; i > 0 && currentWeight > 0; i--) {
            if(dp[i,currentWeight] != dp[i-1,currentWeight]) {
                selected.Add(i-1);
                currentWeight -= weights[i-1];
            }
        }
        
        // Reverse to get items in original order
        selected.Reverse();
        
        return new KnapsackResult {
            MaxValue = dp[n,capacity],
            SelectedItems = selected
        };
    }
    
    public static void Main(string[] args) {
        int[] values = {3, 4, 5, 6};
        int[] weights = {2, 3, 4, 5};
        int capacity = 10;
        
        var result = Solve(values, weights, capacity);
        
        Console.WriteLine($"Maximum value: {result.MaxValue}");
        Console.WriteLine($"Selected items: {string.Join(" ", result.SelectedItems)}");
    }
}

Complexity Analysis

Metric	Complexity	Notes
Time Complexity	O(nW)	n items, W capacity
Space Complexity	O(nW)	DP table size

Notes:

n - Number of items
W - Knapsack capacity
Space can be optimized to O(W) using 1D array
Time complexity is pseudo-polynomial
NP-hard problem in its decision version

Advantages and Disadvantages

Advantages

Finds optimal solution guaranteed
Can handle arbitrary values and weights
Easy to modify for variations
Solution is deterministic
Can be optimized for space

Disadvantages

Pseudo-polynomial time complexity
High memory usage for large capacities
Not suitable for fractional items
Impractical for very large instances
No approximation guarantee if simplified

Quick Info

0/1 Knapsack Problem