0/1 Knap-Sack Dynamic Programming (DP) Approach

The 0/1 Knapsack problem is one of the most popular problems in computer science and is a classic example of how dynamic programming (DP) can be used to solve optimization problems efficiently. The 0/1 Knapsack problem is about choosing items to put in a bag so that you get the maximum value without exceeding the bag’s weight limit. Each item can be taken completely (1) or not at all (0),  you cannot take it in fractions.

Instead of checking all combinations like the brute-force method, Dynamic Programming (DP) makes the process faster by breaking the problem into smaller parts and storing previous results to avoid repeating calculations. This way, you avoid repeating calculations and can find the maximum value efficiently.

What is 0/1 Knapsack Problem?

The 0/1 Knapsack Problem is a classic optimization problem in computer science.

It helps us decide which items to pick from a list so that:

1. Total profit/value is maximized
2. Total weight does not exceed the bag’s capacity
3. Each item can be either taken (1) or not taken (0) → you cannot take fractions of an item

This is why it is called 0/1 knapsack.

Real-Life Example to Understand It

Imagine you have:

• A backpack that can carry 15 kg
• 5 items, each with:
  • weight
  • value (how important/useful it is)

But you cannot carry everything.
You must choose the best combination of items that:

✔ gives maximum total value
✔ but keeps the total weight ≤ 15 kg

This is exactly what the 0/1 Knapsack Problem solves.

Why Dynamic Programming is Used?

1. Naive Approach (Brute Force):

In the Naive or Brute Force approach, we try all possible combinations of items to find the one that gives the maximum total value without crossing the weight limit of the bag.

For every item, we have two choices :

1. Include it in the bag, or
2. Exclude it from the bag.

So, for n items, there are a total of 2ⁿ possible combinations (because each item has 2 choices).

We then calculate the total weight and total value for each combination and pick the one that gives the highest value without going over the bag’s capacity.

However, this method is very slow because as the number of items increases, the number of combinations grows exponentially (for example, 10 items → 1024 combinations, 20 items → 1,048,576 combinations).

That’s why this approach becomes impractical for large n, it takes too long to check every possible subset.

2. DP (Dynamic Programming) Approach:

In the Dynamic Programming (DP) approach, we break the big problem into smaller parts. We use a table, often called dp[i][w], where each cell stores the maximum value that can be achieved using the first i items and a bag capacity of w.

By storing answers to these smaller problems in the table, we can reuse them later instead of calculating the same thing again and again. This helps save a lot of time.

Because of this smart reuse, the time needed to solve the problem becomes O(n × W) (where n is the number of items and W is the total weight capacity), which is much faster than the brute force method.

Formulating the DP Recurrence Equation

Step 1: Define the DP State

We make a table called dp[i][w], where each cell tells us the maximum value we can get using the first i items and a bag capacity of w.

• i goes from 0 to n (number of items)
• w goes from 0 to W (maximum weight of the bag)

So, dp[i][w] helps us remember the best value we can achieve for every smaller combination of items and weight limits.

Step 2: Recurrence Relation (Main Formula)

For each item i, we have two choices:

1. Do not take the item:
   The value remains the same as before:
   dp[i][w] = dp[i - 1][w]
2. Take the item (only if the item’s weight ≤ current bag capacity):
   Add the item’s value and reduce the capacity by its weight:
   dp[i][w] = value[i] + dp[i – 1][w – weight[i]]

After checking both choices, we pick the better (maximum) one:
dp[i][w] = max(dp[i – 1][w], value[i] + dp[i – 1][w – weight[i]])

Step 3: Base Cases

We start by setting up simple starting points:

• No items: If there are no items, we can’t get any value.
  dp[0][w] = 0 for all w
• Capacity 0: If the bag capacity is zero, we can’t add anything.
  dp[i][0] = 0 for all i

Lets see below example to understand it in better way

Example: 0/1 Knap-Sack Dynamic Programming (DP) Approach

Problem statement

You have a bag that can hold up to 50 kg. There are 3 items, each with a specific value and weight. You can either take an item completely or leave it.

Your goal is to choose the items so that the total weight does not exceed 50 kg and the total value is as high as possible. Find the maximum total value you can carry and which items should be chosen.

Items:

• Item 1 → Value = 60, Weight = 10
• Item 2 → Value = 100, Weight = 20
• Item 3 → Value = 120, Weight = 30

Bag Capacity: W = 50

Step 1: Create the DP Table

We create a table dp[4][51] because:

• There are 3 items, so we take n + 1 = 4 rows (including row 0 for no items).
• The bag capacity is 50, so we take W + 1 = 51 columns (including column 0 for capacity 0).

Each cell dp[i][w] will store the maximum value we can get using the first i items and capacity w.

Step 2: Fill the Table Row by Row

Row 1 (Item 1: weight = 10, value = 60)

• For capacities w < 10, we cannot take the item, so:
  dp[1][w] = 0
• For capacities w ≥ 10, we can take the item, so:
  dp[1][w] = 60

Row 2 (Item 2: weight = 20, value = 100)

• For capacities w < 20, we can’t take the new item, so:
  dp[2][w] = dp[1][w] (same as before)
• For capacities w ≥ 20, we have two choices:
  1. Do not take item 2: value = dp[1][w]
  2. Take item 2: value = 100 + dp[1][w - 20]
     We take the maximum of these two.
     So, dp[2][w] = max(dp[1][w], 100 + dp[1][w - 20])

Row 3 (Item 3: weight = 30, value = 120)

• For capacities w < 30, we can’t take this item, so:
  dp[3][w] = dp[2][w]
• For capacities w ≥ 30, again we have two choices:
  1. Do not take item 3: value = dp[2][w]
  2. Take item 3: value = 120 + dp[2][w - 30]
     Take the maximum of these two:
     dp[3][w] = max(dp[2][w], 120 + dp[2][w - 30])

Step 3: Final Result

• The final answer will be in the last cell:
  dp[3][50] = 220
• So, the maximum value we can carry in the bag is 220.
• Selected Items: Item 2 and Item 3.

Time & Space Complexity

For the 0/1 Knapsack Problem using Dynamic Programming, the time and space complexity are as follows:

Time Complexity

Space Complexity

Conclusion

The 0/1 Knapsack problem helps us pick items to get the maximum value without exceeding the bag’s weight. Using Dynamic Programming, we can solve it quickly and efficiently by remembering the best values for smaller subproblems. The DP table shows the maximum value we can get for each number of items and bag capacity, and the last cell gives the final answer. Dynamic Programming makes it practical and easy to find the best solution for the 0/1 Knapsack problem.