Knapsack Problem

Example of a Knapsack Problem

Problem Statement:
You are given a set of items, each with a weight and a value.

You need to determine the number of each item to include in a knapsack so that the total weight is less than or equal to a given limit, and the total value is as large as possible.

Items:

  • Item 1: Weight = $2$, Value = $3$
  • Item 2: Weight = $3$, Value = $4$
  • Item 3: Weight = $4$, Value = $5$
  • Item 4: Weight = $5$, Value = $6$

Knapsack Capacity: $8$

The goal is to maximize the total value without exceeding the knapsack capacity of $8$.

Python Solution:

This is a $dynamic$ $programming$ approach to solve the $0$/$1$ Knapsack Problem.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def knapsack(values, weights, capacity):
    n = len(values)
    # Create a 2D DP table with (n+1) x (capacity+1) size
    dp = [[0 for _ in range(capacity + 1)] for _ in range(n + 1)]

    # Fill the DP table
    for i in range(1, n + 1):
        for w in range(1, capacity + 1):
            if weights[i - 1] <= w:
                dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1])
            else:
                dp[i][w] = dp[i - 1][w]

    # The maximum value will be in dp[n][capacity]
    return dp[n][capacity]

# Example data
values = [3, 4, 5, 6]
weights = [2, 3, 4, 5]
capacity = 8

# Solve the problem
max_value = knapsack(values, weights, capacity)
print("Maximum value that can be carried in the knapsack:", max_value)

Explanation:

  1. Initialization:

    • The function knapsack takes three arguments: values, weights, and capacity.
    • The $dynamic$ $programming$ ($DP$) table dp is initialized with zeros.
      The table has dimensions (n+1) x (capacity+1), where n is the number of items.

  2. Filling the DP Table:

    • The outer loop iterates through the items, and the inner loop iterates through possible capacities from 1 to capacity.
    • For each item and capacity, the $DP$ table is updated by considering two possibilities:
      • Not including the item in the knapsack (value remains the same as the previous row).
      • Including the item in the knapsack (value is updated based on the remaining capacity and the value of the item).

  3. Result:

    • After filling the $DP$ table, the maximum value that can be carried in the knapsack is found in dp[n][capacity].

Output:

1
Maximum value that can be carried in the knapsack: 10

In this example, the optimal solution is to include Item $2$ (weight $3$, value $4$) and Item $4$ (weight $5$, value $6$), which gives a total value of $10$ while staying within the capacity limit of $8$.