Skip to content
My Docs

Knapsack Problem

Generated on 2025-07-10 02:01:29 Algorithm Cheatsheet for Technical Interviews

Knapsack Problem Cheatsheet

Section titled “Knapsack Problem Cheatsheet”

1. Quick Overview

Section titled “1. Quick Overview”

The Knapsack Problem is a classic optimization problem where you have a knapsack with a limited weight capacity and a set of items, each with a weight and a value. The goal is to choose the items that maximize the total value while staying within the weight limit.

When to use it:

  • You need to select a subset of items to maximize profit/value under a weight/size constraint.
  • You encounter scenarios involving resource allocation or budget management.

2. Time & Space Complexity

Section titled “2. Time & Space Complexity”
ApproachTime ComplexitySpace Complexity
Brute ForceO(2n)O(1)
Dynamic Programming (0/1 Knapsack)O(nW)O(nW) or O(W) (optimized)
Dynamic Programming (Unbounded Knapsack)O(nW)O(nW) or O(W) (optimized)
Greedy (Fractional Knapsack)O(n log n)O(1)
  • n: Number of items
  • W: Knapsack capacity

3. Implementation

Section titled “3. Implementation”

Here’s a breakdown of the common implementation strategies:

A. 0/1 Knapsack (Each item can be included only once)

Python:

def knapsack_01(capacity, weights, values, n):
    """
    0/1 Knapsack problem using dynamic programming.


    Args:
        capacity: The maximum weight capacity of the knapsack.
        weights: A list of weights for each item.
        values: A list of values for each item.
        n: The number of items.


    Returns:
        The maximum value that can be put in the knapsack.
    """


    dp = [[0 for _ in range(capacity + 1)] for _ in range(n + 1)]  # dp[i][w] = max value with items up to i and weight w


    for i in range(n + 1):
        for w in range(capacity + 1):
            if i == 0 or w == 0:
                dp[i][w] = 0
            elif weights[i-1] <= w:
                dp[i][w] = max(values[i-1] + dp[i-1][w-weights[i-1]], dp[i-1][w])
            else:
                dp[i][w] = dp[i-1][w]


    return dp[n][capacity]


# Example Usage:
values = [60, 100, 120]
weights = [10, 20, 30]
capacity = 50
n = len(values)
max_value = knapsack_01(capacity, weights, values, n)
print("Maximum value:", max_value)  # Output: 220

Java:

class Knapsack {
    public static int knapsack01(int capacity, int[] weights, int[] values, int n) {
        int[][] dp = new int[n + 1][capacity + 1]; // dp[i][w] = max value with items up to i and weight w


        for (int i = 0; i <= n; i++) {
            for (int w = 0; w <= capacity; w++) {
                if (i == 0 || w == 0) {
                    dp[i][w] = 0;
                } else 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];
                }
            }
        }


        return dp[n][capacity];
    }


    public static void main(String[] args) {
        int[] values = {60, 100, 120};
        int[] weights = {10, 20, 30};
        int capacity = 50;
        int n = values.length;
        int max_value = knapsack01(capacity, weights, values, n);
        System.out.println("Maximum value: " + max_value); // Output: 220
    }
}

C++:

#include <iostream>
#include <vector>
#include <algorithm>


using namespace std;


int knapsack01(int capacity, vector<int>& weights, vector<int>& values, int n) {
    vector<vector<int>> dp(n + 1, vector<int>(capacity + 1, 0)); // dp[i][w] = max value with items up to i and weight w


    for (int i = 0; i <= n; i++) {
        for (int w = 0; w <= capacity; w++) {
            if (i == 0 || w == 0) {
                dp[i][w] = 0;
            } else if (weights[i - 1] <= w) {
                dp[i][w] = max(values[i - 1] + dp[i - 1][w - weights[i - 1]], dp[i - 1][w]);
            } else {
                dp[i][w] = dp[i - 1][w];
            }
        }
    }


    return dp[n][capacity];
}


int main() {
    vector<int> values = {60, 100, 120};
    vector<int> weights = {10, 20, 30};
    int capacity = 50;
    int n = values.size();
    int max_value = knapsack01(capacity, weights, values, n);
    cout << "Maximum value: " << max_value << endl; // Output: 220
    return 0;
}

B. Unbounded Knapsack (Each item can be included multiple times)

Python:

def unbounded_knapsack(capacity, weights, values, n):
    """
    Unbounded Knapsack problem using dynamic programming.


    Args:
        capacity: The maximum weight capacity of the knapsack.
        weights: A list of weights for each item.
        values: A list of values for each item.
        n: The number of items.


    Returns:
        The maximum value that can be put in the knapsack.
    """


    dp = [0] * (capacity + 1) # dp[w] = max value with weight w


    for w in range(1, capacity + 1):
        for i in range(n):
            if weights[i] <= w:
                dp[w] = max(dp[w], dp[w - weights[i]] + values[i])


    return dp[capacity]


# Example Usage:
values = [60, 100, 120]
weights = [10, 20, 30]
capacity = 50
n = len(values)
max_value = unbounded_knapsack(capacity, weights, values, n)
print("Maximum value:", max_value)  # Output: 300

Java:

class UnboundedKnapsack {
    public static int unboundedKnapsack(int capacity, int[] weights, int[] values, int n) {
        int[] dp = new int[capacity + 1]; // dp[w] = max value with weight w


        for (int w = 1; w <= capacity; w++) {
            for (int i = 0; i < n; i++) {
                if (weights[i] <= w) {
                    dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
                }
            }
        }


        return dp[capacity];
    }


    public static void main(String[] args) {
        int[] values = {60, 100, 120};
        int[] weights = {10, 20, 30};
        int capacity = 50;
        int n = values.length;
        int max_value = unboundedKnapsack(capacity, weights, values, n);
        System.out.println("Maximum value: " + max_value); // Output: 300
    }
}

C++:

#include <iostream>
#include <vector>
#include <algorithm>


using namespace std;


int unboundedKnapsack(int capacity, vector<int>& weights, vector<int>& values, int n) {
    vector<int> dp(capacity + 1, 0); // dp[w] = max value with weight w


    for (int w = 1; w <= capacity; w++) {
        for (int i = 0; i < n; i++) {
            if (weights[i] <= w) {
                dp[w] = max(dp[w], dp[w - weights[i]] + values[i]);
            }
        }
    }


    return dp[capacity];
}


int main() {
    vector<int> values = {60, 100, 120};
    vector<int> weights = {10, 20, 30};
    int capacity = 50;
    int n = values.size();
    int max_value = unboundedKnapsack(capacity, weights, values, n);
    cout << "Maximum value: " << max_value << endl; // Output: 300
    return 0;
}

C. Fractional Knapsack (Items can be taken in fractions)

Python:

def fractional_knapsack(capacity, items):
    """
    Fractional Knapsack problem using a greedy approach.


    Args:
        capacity: The maximum weight capacity of the knapsack.
        items: A list of tuples (value, weight) for each item.


    Returns:
        The maximum value that can be put in the knapsack.
    """


    # Calculate value-to-weight ratio for each item
    value_per_weight = [(value / weight, value, weight) for value, weight in items]


    # Sort items by value-to-weight ratio in descending order
    value_per_weight.sort(reverse=True)


    total_value = 0
    remaining_capacity = capacity


    for ratio, value, weight in value_per_weight:
        if weight <= remaining_capacity:
            total_value += value
            remaining_capacity -= weight
        else:
            fraction = remaining_capacity / weight
            total_value += value * fraction
            break  # Knapsack is full


    return total_value




# Example Usage:
items = [(60, 10), (100, 20), (120, 30)]
capacity = 50
max_value = fractional_knapsack(capacity, items)
print("Maximum value:", max_value)  # Output: 240.0

Java:

import java.util.Arrays;
import java.util.Comparator;


class FractionalKnapsack {
    public static double fractionalKnapsack(int capacity, Item[] items) {
        // Calculate value-to-weight ratio for each item
        Arrays.sort(items, Comparator.comparingDouble(item -> -item.value / (double) item.weight));


        double totalValue = 0;
        int remainingCapacity = capacity;


        for (Item item : items) {
            if (item.weight <= remainingCapacity) {
                totalValue += item.value;
                remainingCapacity -= item.weight;
            } else {
                double fraction = (double) remainingCapacity / item.weight;
                totalValue += item.value * fraction;
                break; // Knapsack is full
            }
        }


        return totalValue;
    }


    public static void main(String[] args) {
        Item[] items = {new Item(60, 10), new Item(100, 20), new Item(120, 30)};
        int capacity = 50;
        double maxValue = fractionalKnapsack(capacity, items);
        System.out.println("Maximum value: " + maxValue); // Output: 240.0
    }


    static class Item {
        int value;
        int weight;


        public Item(int value, int weight) {
            this.value = value;
            this.weight = weight;
        }
    }
}

C++:

#include <iostream>
#include <vector>
#include <algorithm>


using namespace std;


struct Item {
    int value;
    int weight;
    double valuePerWeight;


    Item(int v, int w) : value(v), weight(w) {
        valuePerWeight = (double)v / w;
    }
};


bool compareItems(const Item& a, const Item& b) {
    return a.valuePerWeight > b.valuePerWeight;
}


double fractionalKnapsack(int capacity, vector<Item>& items) {
    sort(items.begin(), items.end(), compareItems);


    double totalValue = 0.0;
    int remainingCapacity = capacity;


    for (const auto& item : items) {
        if (item.weight <= remainingCapacity) {
            totalValue += item.value;
            remainingCapacity -= item.weight;
        } else {
            double fraction = (double)remainingCapacity / item.weight;
            totalValue += item.value * fraction;
            break;
        }
    }


    return totalValue;
}


int main() {
    vector<Item> items = {Item(60, 10), Item(100, 20), Item(120, 30)};
    int capacity = 50;
    double maxValue = fractionalKnapsack(capacity, items);
    cout << "Maximum value: " << maxValue << endl; // Output: 240.0
    return 0;
}

4. Common Patterns

Section titled “4. Common Patterns”
  • 0/1 Knapsack: Decision to include or exclude each item.
  • Unbounded Knapsack: Items can be included multiple times. Coin Change is a variation of this.
  • Fractional Knapsack: Items can be taken in fractions (greedy approach). Useful where divisibility makes sense.
  • Variations:
    • Minimum number of items to achieve a specific value.
    • Target Sum (subset sum problem).

5. Pro Tips

Section titled “5. Pro Tips”
  • Space Optimization: For 0/1 and Unbounded Knapsack, you can reduce space complexity from O(nW) to O(W) by using a 1D DP array. Iterate in reverse order for 0/1 Knapsack to avoid overwriting values you’ll need later. Iterate in forward order for unbounded knapsack.
  • Initialization: Correctly initialize the DP table. dp[0][w] and dp[i][0] are often initialized to 0.
  • Edge Cases: Handle cases where the knapsack capacity is 0 or the number of items is 0.
  • Early Exit: In Fractional Knapsack, exit the loop as soon as the knapsack is full.
  • Integer Overflow: Be mindful of integer overflow when calculating values. Use larger data types if necessary.

6. Practice Problems

Section titled “6. Practice Problems”
  • LeetCode 416. Partition Equal Subset Sum: (0/1 Knapsack variation) Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.
  • LeetCode 322. Coin Change: (Unbounded Knapsack variation) You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.
  • GeeksforGeeks - Fractional Knapsack: Given weights and values of N items, we need to put these items in a knapsack of capacity W to get the maximum total value in the knapsack. In Fractional Knapsack, we can break items for maximizing the total value of the knapsack.

7. Templates

Section titled “7. Templates”

Here are code templates to get you started quickly:

Python:

def knapsack_template(capacity, weights, values, n, type="0/1"):
    """
    Template for Knapsack problem.


    Args:
        capacity: The maximum weight capacity of the knapsack.
        weights: A list of weights for each item.
        values: A list of values for each item.
        n: The number of items.
        type: "0/1", "unbounded", "fractional"


    Returns:
        The maximum value that can be put in the knapsack.
    """


    if type == "0/1":
        # 0/1 Knapsack implementation (DP)
        dp = [[0 for _ in range(capacity + 1)] for _ in range(n + 1)]
        for i in range(n + 1):
            for w in range(capacity + 1):
                if i == 0 or w == 0:
                    dp[i][w] = 0
                elif weights[i-1] <= w:
                    dp[i][w] = max(values[i-1] + dp[i-1][w-weights[i-1]], dp[i-1][w])
                else:
                    dp[i][w] = dp[i-1][w]
        return dp[n][capacity]
    elif type == "unbounded":
        # Unbounded Knapsack implementation (DP)
        dp = [0] * (capacity + 1)
        for w in range(1, capacity + 1):
            for i in range(n):
                if weights[i] <= w:
                    dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
        return dp[capacity]


    elif type == "fractional":
        # Fractional Knapsack Implementation (Greedy)
        items = list(zip(values, weights))
        value_per_weight = [(value / weight, value, weight) for value, weight in items]
        value_per_weight.sort(reverse=True)
        total_value = 0
        remaining_capacity = capacity


        for ratio, value, weight in value_per_weight:
            if weight <= remaining_capacity:
                total_value += value
                remaining_capacity -= weight
            else:
                fraction = remaining_capacity / weight
                total_value += value * fraction
                break
        return total_value


    else:
        return -1 # Or raise an exception


# Example Usage:
values = [60, 100, 120]
weights = [10, 20, 30]
capacity = 50
n = len(values)
max_value_01 = knapsack_template(capacity, weights, values, n, "0/1")
max_value_unbounded = knapsack_template(capacity, weights, values, n, "unbounded")
max_value_fractional = knapsack_template(capacity, weights, values, n, "fractional")


print("Maximum value (0/1):", max_value_01)
print("Maximum value (unbounded):", max_value_unbounded)
print("Maximum value (fractional):", max_value_fractional)

Java:

class KnapsackTemplate {


    public static int knapsackTemplate(int capacity, int[] weights, int[] values, int n, String type) {
        if (type.equals("0/1")) {
            // 0/1 Knapsack implementation (DP)
            int[][] dp = new int[n + 1][capacity + 1];
            for (int i = 0; i <= n; i++) {
                for (int w = 0; w <= capacity; w++) {
                    if (i == 0 || w == 0) {
                        dp[i][w] = 0;
                    } else 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];
                    }
                }
            }
            return dp[n][capacity];
        } else if (type.equals("unbounded")) {
            // Unbounded Knapsack implementation (DP)
            int[] dp = new int[capacity + 1];
            for (int w = 1; w <= capacity; w++) {
                for (int i = 0; i < n; i++) {
                    if (weights[i] <= w) {
                        dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
                    }
                }
            }
            return dp[capacity];
        } else if (type.equals("fractional")) {
            // Fractional Knapsack implementation (Greedy)
            Item[] items = new Item[n];
            for(int i = 0; i < n; i++){
                items[i] = new Item(values[i], weights[i]);
            }
            Arrays.sort(items, Comparator.comparingDouble(item -> -item.value / (double) item.weight));
            double totalValue = 0;
            int remainingCapacity = capacity;


            for (Item item : items) {
                if (item.weight <= remainingCapacity) {
                    totalValue += item.value;
                    remainingCapacity -= item.weight;
                } else {
                    double fraction = (double) remainingCapacity / item.weight;
                    totalValue += item.value * fraction;
                    break;
                }
            }
            return (int) totalValue;
        } else {
            return -1; // Or throw an exception
        }
    }


    static class Item {
        int value;
        int weight;


        public Item(int value, int weight) {
            this.value = value;
            this.weight = weight;
        }
    }


    public static void main(String[] args) {
        int[] values = {60, 100, 120};
        int[] weights = {10, 20, 30};
        int capacity = 50;
        int n = values.length;


        int max_value_01 = knapsackTemplate(capacity, weights, values, n, "0/1");
        int max_value_unbounded = knapsackTemplate(capacity, weights, values, n, "unbounded");
        int max_value_fractional = knapsackTemplate(capacity, weights, values, n, "fractional");


        System.out.println("Maximum value (0/1): " + max_value_01);
        System.out.println("Maximum value (unbounded): " + max_value_unbounded);
        System.out.println("Maximum value (fractional): " + max_value_fractional);
    }
}

C++:

#include <iostream>
#include <vector>
#include <algorithm>


using namespace std;


struct Item {
    int value;
    int weight;
    double valuePerWeight;


    Item(int v, int w) : value(v), weight(w) {
        valuePerWeight = (double)v / w;
    }
};


bool compareItems(const Item& a, const Item& b) {
    return a.valuePerWeight > b.valuePerWeight;
}


int knapsackTemplate(int capacity, vector<int>& values, vector<int>& weights, int n, string type) {
    if (type == "0/1") {
        // 0/1 Knapsack implementation (DP)
        vector<vector<int>> dp(n + 1, vector<int>(capacity + 1, 0));
        for (int i = 0; i <= n; i++) {
            for (int w = 0; w <= capacity; w++) {
                if (i == 0 || w == 0) {
                    dp[i][w] = 0;
                } else if (weights[i - 1] <= w) {
                    dp[i][w] = max(values[i - 1] + dp[i - 1][w - weights[i - 1]], dp[i - 1][w]);
                } else {
                    dp[i][w] = dp[i - 1][w];
                }
            }
        }
        return dp[n][capacity];
    } else if (type == "unbounded") {
        // Unbounded Knapsack implementation (DP)
        vector<int> dp(capacity + 1, 0);
        for (int w = 1; w <= capacity; w++) {
            for (int i = 0; i < n; i++) {
                if (weights[i] <= w) {
                    dp[w] = max(dp[w], dp[w - weights[i]] + values[i]);
                }
            }
        }
        return dp[capacity];
    } else if (type == "fractional") {
        // Fractional Knapsack implementation (Greedy)
        vector<Item> items;
        for(int i = 0; i < n; i++){
            items.emplace_back(values[i], weights[i]);
        }
        sort(items.begin(), items.end(), compareItems);


        double totalValue = 0.0;
        int remainingCapacity = capacity;


        for (const auto& item : items) {
            if (item.weight <= remainingCapacity) {
                totalValue += item.value;
                remainingCapacity -= item.weight;
            } else {
                double fraction = (double)remainingCapacity / item.weight;
                totalValue += item.value * fraction;
                break;
            }
        }
        return (int)totalValue;
    } else {
        return -1; // Or throw an exception
    }
}


int main() {
    vector<int> values = {60, 100, 120};
    vector<int> weights = {10, 20, 30};
    int capacity = 50;
    int n = values.size();


    int max_value_01 = knapsackTemplate(capacity, values, weights, n, "0/1");
    int max_value_unbounded = knapsackTemplate(capacity, values, weights, n, "unbounded");
    int max_value_fractional = knapsackTemplate(capacity, values, weights, n, "fractional");


    cout << "Maximum value (0/1): " << max_value_01 << endl;
    cout << "Maximum value (unbounded): " << max_value_unbounded << endl;
    cout << "Maximum value (fractional): " << max_value_fractional << endl;


    return 0;
}

This comprehensive cheatsheet provides a solid foundation for understanding and applying the Knapsack Problem in various scenarios. Remember to tailor the code and techniques to the specific requirements of the problem at hand. Good luck!