Data Structures and Algorithms (DSA)  

0/1 Knapsack Problem in Dynamic Programming (DSA)

Introduction

The 0/1 Knapsack Problem is one of the most important and frequently asked Dynamic Programming (DP) problems in DSA interviews. It is used to test your understanding of decision making, optimization, and DP table construction.

In simple words, this problem is about choosing the best items to put into a bag so that the total value is maximum, without exceeding the bag’s capacity.

This article explains the 0/1 Knapsack problem in very simple language, step by step, from basics to interview-level understanding.

What is the Knapsack Problem?

The word knapsack means a bag. In this problem:

  • You are given a bag with a fixed capacity

  • You are given items, each with:

    • A weight

    • A value

Your goal is to maximize the total value of items placed in the bag without exceeding its capacity.

Why is it Called 0/1 Knapsack?

The name 0/1 Knapsack means:

  • You can either take an item (1)

  • Or leave an item (0)

You cannot take the same item more than once. There is no partial selection.

This is what makes it different from other knapsack problems.

Problem Statement

You are given:

  • An array weights[]

  • An array values[]

  • An integer W (capacity of the knapsack)

Find the maximum total value that can be obtained.

Example

weights = [1, 3, 4, 5]
values  = [1, 4, 5, 7]
W = 7

Output

9

Explanation

Items with weight 3 and 4 give maximum value:

4 + 5 = 9

Why Brute Force is Not Practical

In brute force, we try all possible combinations of items.

Problems with Brute Force

  • Number of combinations grows exponentially

  • Time complexity becomes very large

This approach is not suitable for interviews.

Dynamic Programming Approach (Core Concept)

Dynamic Programming helps us avoid repeated calculations.

Key Idea

For each item, we decide:

  • Include the item

  • Exclude the item

We store results of smaller subproblems to build the final answer.

DP Table Explanation

We create a 2D DP table:

  • dp[i][w] = maximum value using first i items with capacity w

Table Size

  • Rows → number of items + 1

  • Columns → capacity + 1

Step-by-Step DP Logic

Steps:

  1. Initialize DP table with 0

  2. For each item:

    • For each capacity:

      • If item weight ≤ capacity:

        • Choose max of include or exclude

      • Else:

        • Exclude the item

  3. Final answer is at dp[n][W]

Dry Run Example

Items \ Capacity01234567
0 items00000000
Item 101111111
Item 201145555
Item 301145669

Final Answer = 9

Code Implementation

C++ Code

int knapsack(int W, vector<int>& weights, vector<int>& values) {
    int n = weights.size();
    vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));

    for (int i = 1; i <= n; i++) {
        for (int w = 1; w <= W; w++) {
            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][W];
}

Java Code

public int knapsack(int W, int[] weights, int[] values) {
    int n = weights.length;
    int[][] dp = new int[n + 1][W + 1];

    for (int i = 1; i <= n; i++) {
        for (int w = 1; w <= W; 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];
            }
        }
    }
    return dp[n][W];
}

Python Code

def knapsack(W, weights, values):
    n = len(weights)
    dp = [[0] * (W + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for w in range(1, W + 1):
            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][W]

Time and Space Complexity

  • Time Complexity: O(n × W)

  • Space Complexity: O(n × W)

This is acceptable for most interview constraints.

Important Edge Cases

  • Capacity is 0

  • No items given

  • All item weights greater than capacity

Always mention these in interviews.

Common Interview Variations

  • Space optimized knapsack

  • Unbounded knapsack

  • Fractional knapsack

  • Print selected items

Understanding 0/1 Knapsack makes these easier.

Summary

The 0/1 Knapsack Problem is a cornerstone of Dynamic Programming in DSA. It teaches how to make optimal decisions by breaking a problem into smaller subproblems and storing results. By mastering the DP table approach and understanding include/exclude logic, you build strong foundations for solving many advanced optimization problems in coding interviews.

Membership not found