Top 5 Interview Problems in Advanced Data Structures and Algorithms (DSA)

Chapter 5: Solving the Knapsack Problem using Dynamic Programming

Introduction

The Knapsack Problem is one of the most important problems in combinatorial optimization. It involves selecting items from a given set of items, each with a weight and a value, such that the total weight is less than or equal to a given capacity and the total value is maximized. This problem has numerous applications in real-world scenarios like resource allocation, budget management, cargo loading, and more.

There are multiple variations of the Knapsack Problem, but the most common and well-studied is the 0/1 Knapsack Problem, where each item can either be included in the knapsack or excluded (i.e., you cannot take fractional items).

In this chapter, we will focus on solving the 0/1 Knapsack Problem using Dynamic Programming (DP). Dynamic programming provides an efficient way to solve the problem by breaking it down into smaller subproblems and solving them optimally, which avoids redundant calculations and significantly improves performance compared to brute-force approaches.

We will explore:

• The formulation of the 0/1 Knapsack Problem.
• The dynamic programming approach to solving the Knapsack problem.
• Optimizations to the DP solution to reduce space complexity.
• Practical applications of the Knapsack Problem.

By the end of this chapter, you will have a strong understanding of how to approach the Knapsack Problem using dynamic programming and how to apply these techniques to solve related problems efficiently.

1. Problem Statement: The 0/1 Knapsack Problem

In the 0/1 Knapsack Problem, you are given:

1. A set of n items, each with a weight w_i​ and a value v_i​.
2. A capacity W of the knapsack.

The objective is to find the maximum total value that can be obtained by selecting items such that their total weight does not exceed the knapsack's capacity.

Formally, the problem is defined as:

Subject to:

Where  x_i ∈ { 0, 1 } is the decision variable representing whether item i is included (1) or excluded (0) from the knapsack.

Example:

Consider the following items and their corresponding values and weights:

The knapsack has a capacity W = 5.

We need to find the subset of items that maximizes the total value while not exceeding the capacity of 5. The optimal solution is to include items 1 and 2, which gives a total value of 7 and a total weight of 5.

2. Dynamic Programming Solution

Dynamic programming solves the 0/1 Knapsack Problem by breaking it into smaller subproblems. The key idea is to build a table that stores the maximum value that can be achieved for each subproblem. We solve the subproblems incrementally and use their results to solve the larger problem.

Step-by-step Approach:

1. Define a DP table: Let dp[i][w] be the maximum value that can be obtained with the first i items and a knapsack capacity of w.
2. Recurrence Relation: For each item iii and each possible weight www, we have two choices:
• Exclude the item: The maximum value is the same as the maximum value for the previous item with the same capacity, i.e., dp[i-1][w].
• Include the item (if w_i ≤  w): The maximum value is the value of the item plus the maximum value for the remaining capacity, i.e., v_i + dp[i-1][w - w_i].

The recurrence relation is:

Otherwise:

3. Base Case:
• If there are no items or the knapsack capacity is zero, the maximum value is zero: dp[0][w] = 0 for all w, and dp[i][0] = 0 for all i.

Code Sample: 0/1 Knapsack Problem using Dynamic Programming

def knapsack(values, weights, W, n):

    # Create a 2D DP table with (n+1) rows and (W+1) columns

    dp = [[0 for _ in range(W + 1)] for _ in range(n + 1)]

    # Build the DP table

    for i in range(1, n + 1):

        for w in range(1, W + 1):

            if weights[i - 1] <= w:

                dp[i][w] = max(dp[i - 1][w], values[i - 1] + dp[i - 1][w - weights[i - 1]])

            else:

                dp[i][w] = dp[i - 1][w]

    # The maximum value will be in the bottom-right cell

    return dp[n][W]

# Example usage

values = [3, 4, 5, 8]

weights = [2, 3, 4, 5]

W = 5  # Knapsack capacity

n = len(values)

max_value = knapsack(values, weights, W, n)

print(f"Maximum value in Knapsack: {max_value}")

Explanation:

• We create a 2D table dp where dp[i][w] stores the maximum value for the first i items and a knapsack capacity w.
• The table is filled using the recurrence relation based on whether the item is included or excluded.
• The value at dp[n][W] will be the answer, representing the maximum value that can be achieved with n items and knapsack capacity W.

Time Complexity:

• The time complexity of this solution is O(n⋅W), where n is the number of items and W is the capacity of the knapsack.

Space Complexity:

• The space complexity is O(n⋅W), as we need to store the DP table.

3. Optimizing Space Complexity

The DP solution above requires a 2D table of size O(n⋅W), which can be quite memory-intensive when the number of items or the capacity is large. However, since we only need the current and previous rows of the table to compute the next row, we can optimize the space complexity by using a 1D array instead of a 2D table.

Code Sample: Optimized Space Complexity

def knapsack_optimized(values, weights, W, n):

    dp = [0 for _ in range(W + 1)]

    for i in range(1, n + 1):

        # Traverse in reverse to ensure we are using the previous row values

        for w in range(W, weights[i - 1] - 1, -1):

            dp[w] = max(dp[w], values[i - 1] + dp[w - weights[i - 1]])

    return dp[W]

# Example usage

values = [3, 4, 5, 8]

weights = [2, 3, 4, 5]

W = 5

n = len(values)

max_value = knapsack_optimized(values, weights, W, n)

print(f"Maximum value in Knapsack (Optimized): {max_value}")

Explanation:

• We use a 1D array dp of size W + 1 to store the maximum values for each possible weight.
• We iterate over the items and update the dp array in reverse order to avoid overwriting the current values during iteration.

Time Complexity:

• The time complexity remains O(n⋅W), but the space complexity is reduced to O(W), as we only need a 1D array.

4. Variants of the Knapsack Problem

While the 0/1 Knapsack Problem is the most common variant, there are several other types of knapsack problems, including:

1. Fractional Knapsack Problem: In this variant, items can be broken into fractions, allowing a partial inclusion of items. This problem can be solved using a greedy algorithm.
2. Multiple Knapsack Problem: In this variant, we have multiple knapsacks with different capacities, and we need to maximize the total value across all knapsacks.
3. Unbounded Knapsack Problem: Here, items can be repeated any number of times (unlimited supply), unlike the 0/1 knapsack where each item can only be used once.

Each of these variants requires different approaches, but the dynamic programming approach is typically used for the 0/1 Knapsack Problem and can be adapted for other variants as well.

5. Real-World Applications of the Knapsack Problem

The Knapsack Problem and its variants are widely used in several real-world scenarios:

1. Resource Allocation: Optimally selecting tasks or resources to maximize profit while staying within budget or capacity constraints.
2. Cargo Loading: Deciding which items to load onto a truck or container to maximize profit while adhering to weight restrictions.
3. Portfolio Selection: Selecting a set of investment options (stocks, bonds, etc.) to maximize returns while staying within a budget.
4. Memory Management: Deciding how to allocate memory or disk space to maximize efficiency while avoiding overflow or exceeding available capacity.

6. Conclusion

In this chapter, we have explored how to solve the 0/1 Knapsack Problem using Dynamic Programming. We covered:

1. The problem statement and formulation of the 0/1 Knapsack Problem.
2. The dynamic programming solution with both a 2D and space-optimized 1D approach.
3. The time and space complexity analysis of the solution.
4. Variants of the knapsack problem, such as the fractional knapsack and multiple knapsack problems.
5. Real-world applications of the knapsack problem in various industries.

By mastering the Knapsack Problem and Dynamic Programming, you will be equipped to solve a wide range of optimization problems efficiently.