Day 33

Day 33: The Knapsack Problem

33/60 Days

The Knapsack Problem #

Welcome to Day 33 of our 60 Days of Coding Algorithm Challenge! Today, we’ll explore the Knapsack Problem, a fundamental problem in combinatorial optimization and a classic example of dynamic programming.

What is the Knapsack Problem? #

The Knapsack Problem is an optimization problem where we need to select items from a set, each with a weight and a value, to maximize the total value while keeping the total weight within a given limit.

There are two main variants of the Knapsack Problem:

0/1 Knapsack Problem: Each item can be included only once or not at all.
Unbounded Knapsack Problem: Each item can be included any number of times.

We’ll focus on the 0/1 Knapsack Problem in this lesson.

Problem Statement #

Given weights and values of n items, put these items in a knapsack of capacity W to get the maximum total value in the knapsack.

Naive Recursive Approach #

Let’s start with a naive recursive implementation:

 1def knapsack_naive(W, wt, val, n):
 2    # Base Case
 3    if n == 0 or W == 0:
 4        return 0
 5
 6    # If weight of the nth item is more than Knapsack capacity W,
 7    # then this item cannot be …

The Knapsack Problem #

What is the Knapsack Problem? #

There are two main variants of the Knapsack Problem:

0/1 Knapsack Problem: Each item can be included only once or not at all.
Unbounded Knapsack Problem: Each item can be included any number of times.

We’ll focus on the 0/1 Knapsack Problem in this lesson.

Problem Statement #

Given weights and values of n items, put these items in a knapsack of capacity W to get the maximum total value in the knapsack.

Naive Recursive Approach #

Let’s start with a naive recursive implementation:

 1def knapsack_naive(W, wt, val, n):
 2    # Base Case
 3    if n == 0 or W == 0:
 4        return 0
 5
 6    # If weight of the nth item is more than Knapsack capacity W,
 7    # then this item cannot be included in the optimal solution
 8    if wt[n-1] > W:
 9        return knapsack_naive(W, wt, val, n-1)
10
11    # Return the maximum of two cases:
12    # (1) nth item included
13    # (2) not included
14    else:
15        return max(
16            val[n-1] + knapsack_naive(W-wt[n-1], wt, val, n-1),
17            knapsack_naive(W, wt, val, n-1)
18        )
19
20# Example usage
21val = [60, 100, 120]
22wt = [10, 20, 30]
23W = 50
24n = len(val)
25print(f"Maximum value: {knapsack_naive(W, wt, val, n)}")

This approach has a time complexity of O(2^n), making it inefficient for larger inputs.

Dynamic Programming Approach #

We can significantly improve the efficiency using Dynamic Programming.

Top-Down Approach (Memoization) #

 1def knapsack_memo(W, wt, val, n, memo=None):
 2    if memo is None:
 3        memo = {}
 4
 5    # Base Case
 6    if n == 0 or W == 0:
 7        return 0
 8
 9    # Check if already computed
10    if (W, n) in memo:
11        return memo[(W, n)]
12
13    # If weight of the nth item is more than Knapsack capacity W,
14    # then this item cannot be included in the optimal solution
15    if wt[n-1] > W:
16        result = knapsack_memo(W, wt, val, n-1, memo)
17    else:
18        # Return the maximum of two cases:
19        # (1) nth item included
20        # (2) not included
21        result = max(
22            val[n-1] + knapsack_memo(W-wt[n-1], wt, val, n-1, memo),
23            knapsack_memo(W, wt, val, n-1, memo)
24        )
25
26    # Save the result in memo
27    memo[(W, n)] = result
28    return result
29
30# Example usage
31val = [60, 100, 120]
32wt = [10, 20, 30]
33W = 50
34n = len(val)
35print(f"Maximum value: {knapsack_memo(W, wt, val, n)}")

Bottom-Up Approach (Tabulation) #

 1def knapsack_tab(W, wt, val, n):
 2    K = [[0 for _ in range(W + 1)] for _ in range(n + 1)]
 3
 4    # Build table K[][] in bottom up manner
 5    for i in range(n + 1):
 6        for w in range(W + 1):
 7            if i == 0 or w == 0:
 8                K[i][w] = 0
 9            elif wt[i-1] <= w:
10                K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]], K[i-1][w])
11            else:
12                K[i][w] = K[i-1][w]
13
14    return K[n][W]
15
16# Example usage
17val = [60, 100, 120]
18wt = [10, 20, 30]
19W = 50
20n = len(val)
21print(f"Maximum value: {knapsack_tab(W, wt, val, n)}")

Both Dynamic Programming approaches have a time complexity of O(nW) and a space complexity of O(nW).

Space-Optimized Solution #

We can optimize the space complexity to O(W) by only keeping track of the current and previous rows of the DP table:

 1def knapsack_space_optimized(W, wt, val, n):
 2    prev = [0] * (W + 1)
 3    curr = [0] * (W + 1)
 4
 5    for i in range(1, n + 1):
 6        for w in range(1, W + 1):
 7            if wt[i-1] <= w:
 8                curr[w] = max(val[i-1] + prev[w-wt[i-1]], prev[w])
 9            else:
10                curr[w] = prev[w]
11        prev, curr = curr, prev
12
13    return prev[W]
14
15# Example usage
16val = [60, 100, 120]
17wt = [10, 20, 30]
18W = 50
19n = len(val)
20print(f"Maximum value: {knapsack_space_optimized(W, wt, val, n)}")

This optimized version has a space complexity of O(W) while maintaining the time complexity of O(nW).

Printing the Selected Items #

We can modify our solution to also print the items that were selected:

 1def knapsack_with_items(W, wt, val, n):
 2    K = [[0 for _ in range(W + 1)] for _ in range(n + 1)]
 3
 4    for i in range(n + 1):
 5        for w in range(W + 1):
 6            if i == 0 or w == 0:
 7                K[i][w] = 0
 8            elif wt[i-1] <= w:
 9                K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]], K[i-1][w])
10            else:
11                K[i][w] = K[i-1][w]
12
13    # Find the selected items
14    res = K[n][W]
15    w = W
16    selected = []
17    for i in range(n, 0, -1):
18        if res <= 0:
19            break
20        if res == K[i-1][w]:
21            continue
22        else:
23            selected.append(i-1)
24            res -= val[i-1]
25            w -= wt[i-1]
26
27    return K[n][W], selected[::-1]
28
29# Example usage
30val = [60, 100, 120]
31wt = [10, 20, 30]
32W = 50
33n = len(val)
34max_value, selected_items = knapsack_with_items(W, wt, val, n)
35print(f"Maximum value: {max_value}")
36print(f"Selected items (indices): {selected_items}")

Applications of the Knapsack Problem #

Resource Allocation in Finance
Cargo Loading
Cutting Stock Problems
Cryptography (in creating pseudorandom number generators)
Combinatorics and Computational Complexity Theory

Exercise #

Implement the Unbounded Knapsack Problem, where you can use items any number of times.
Solve the Subset Sum Problem using the Knapsack algorithm. Given a set of integers and a target sum, determine if there’s a subset that adds up to the target.
Implement a function to solve the Knapsack Problem where items have a volume constraint in addition to weight.

Summary #

Today, we explored the Knapsack Problem, a fundamental problem in combinatorial optimization and a classic example of dynamic programming. We implemented various approaches, from naive recursion to optimized dynamic programming solutions, and even a space-optimized version.

Understanding the Knapsack Problem and its solutions provides valuable insights into dynamic programming techniques and their applications in optimization problems.

Tomorrow, we’ll dive into graph algorithms, starting with Breadth-First Search (BFS). Stay tuned!

The Knapsack Problem #

What is the Knapsack Problem? #

Problem Statement #

Naive Recursive Approach #

The Knapsack Problem #

What is the Knapsack Problem? #

Problem Statement #

Naive Recursive Approach #

Dynamic Programming Approach #

Top-Down Approach (Memoization) #

Bottom-Up Approach (Tabulation) #

Space-Optimized Solution #

Printing the Selected Items #

Applications of the Knapsack Problem #

Exercise #

Summary #

Continue Reading

Re-enter Password

Confirm Action