The 0/1 Knapsack Problem is a famous problem in computer science and optimization.
It’s about finding the best way to pack items into a bag with a weight limit. Each item has its own weight and value. The goal is to get the maximum total value in the bag without exceeding the weight limit. This problem is solved by Dynamic Programming.
The fractional knapsack problem is solved by Greedy Method. If you have not understood the concept, then you can go to the fractional knapsack problem.
.
How to Solve the Problem
To solve this, you look at each item and decide “yes” or “no” (0 or 1, hence the name of the problem). This decision is based on the item’s weight and value, as well as the remaining capacity of the knapsack.
The 0/1 Knapsack Problem involves choosing whether to include each of several items in a knapsack. Each item can either be completely included or completely excluded (you can’t take just a part of an item).
For example, if you have 4 items, you can represent the different combinations of items you might include in your knapsack with a set of four numbers, where each number is either 0 (item not included) or 1 (item included).
Here are some possible combinations for 4 items:
Solution 1 = {0, 0, 0, 0} (no items included)
Solution 2 = {0, 0, 0, 1} (only the fourth item is included)
Solution 3 = {0, 0, 1, 0} (only the third item is included)
Solution 4 = {0, 0, 1, 1} (only the third & fourth items are included)
…
Solution 16 = {1, 1, 1, 1} (all items included)
Since each item can be either in or out, there are 24 (or 16) possible combinations to consider. Thus, if you were to check every possible combination of n items, the number of combinations would be 2n, which means the time complexity of checking all combinations is O(2n).
However, to make the process more efficient and avoid checking each combination one by one, we use a method called dynamic programming. This method helps us optimize the selection process and find the best solution faster than evaluating every possible combination.
.
Origins and Mathematical Basis
The mathematical formulation of the problem can be traced back to the early 20th century, although the exact origins are difficult to pinpoint.
The term “knapsack” comes from the imagery of filling a backpack (or knapsack) of travellers without overloading it beyond its capacity.
.
Development and Computational Complexity
The problem is known for its NP-completeness, a concept formalized in the early 1970s by Stephen Cook and, independently, by Leonid Levin.
NP-completeness means that no efficient algorithm is known that can solve all instances of this problem optimally within polynomial time, and it is believed that no such algorithm exists. This puts the 0/1 Knapsack Problem in the company of many other hard combinatorial optimization problems.
.
Algorithm of 0/1 Knapsack Problem
- n items numbered from 1 to n.
- Each item i has a weight w_i and a profit p_i.
- A knapsack with a weight capacity W.
- Define the DP Table
- Let dp[i][j] represent the maximum value achievable using the first i items with a knapsack capacity of j.
- The table will have n+1 rows (for each item plus one for the case with zero items) and W+1 columns (for each weight from 0 to W).
- Initialize the DP Table
- Set dp[0][j] = 0 for all j from 0 to W. This represents the scenario where no items are included, and thus the value is 0.
- Set dp[i][0] = 0 for all i from 0 to n. This represents the scenario where the capacity of the knapsack is 0, and thus no items can be included.
- Fill the DP Table
- For each item i (from 1 to n):
- For each capacity j (from 1 to W)
- If the item i can be included in the knapsack (i.e., if w_i <= j):
- dp[i][j] = max(dp[i-1][j], dp[i-1][j-w_i] + p_i)
- dp[i-1][j] is the profit without including item i.
- dp[i-1][j-w_i] + p_i is the profit including item i.
- Otherwise:
- dp[i][j] = dp[i-1][j]
- dp[i][j] = max(dp[i-1][j], dp[i-1][j-w_i] + p_i)
- If the item i can be included in the knapsack (i.e., if w_i <= j):
- For each capacity j (from 1 to W)
- For each item i (from 1 to n):
- Retrieve the Maximum Profit
- The profit dp[n][W] represents the maximum profit that can be achieved with n items and a knapsack capacity of W.
Hey! Hey! Hey! STOP… I want to ask a Question.
Question – In the ‘Development and Computational Complexity’ section, we first mentioned that no algorithms exist for the 0/1 Knapsack Problem because this problem is np-complete problem. However, later in the text, we actually describe algorithms that solve this problem. This appears contradictory.
Answer – The algorithm may not efficiently solve the problem for all possible input sizes or in polynomial time due to its NP-complete status. This means that while an algorithm can always be written, there isn’t a universally efficient algorithm (in polynomial time) that solves every instance of the problem optimally.
As the number of items (n) or the capacity of the knapsack (W) becomes very large, the time complexity of known algorithms like dynamic programming, which typically runs in O(nW), which is a pseudo-polynomial complexity, becomes impractical. In such cases, even though an algorithm exists, the computational resources required to execute it would be prohibitive.
- Polynomial Complexity: For polynomial complexity, the running time would depend purely on 𝑛, such as 𝑂(𝑛2), 𝑂(𝑛3), etc.
- Pseudo-Polynomial Complexity: In 𝑂(𝑛𝑊), the term 𝑊 does not refer to the size of the input in the traditional sense (number of elements), but to the numeric value of the weight capacity. This is why it is considered pseudo-polynomial.
The connection between pseudo-polynomial time algorithms and NP-completeness often arises in discussions because many NP-complete problems, like the 0/1 Knapsack problem, can have solutions that run in pseudo-polynomial time.
.
Example
Number of Items (n) – 4
Knapsack Maximum Weight (W) – 8 kg
Items’ Weights (wi) – {2, 3, 4, 5}
Items’ Profits (Pi) – {1, 2, 5, 6}
.
The table will have n+1 rows (for each item plus one for the case with zero items) and W+1 columns (for each weight from 0 to W).
The knapsack has a capacity of 8 kg, so we need a dynamic programming table with 9 columns representing capacities from 0 kg to 8 kg, incrementally increasing by 1 kg from 0 to 8 kg.
There are 4 items, so we need 5 rows representing items from 0 to 4, incrementally increasing by 1 item from 0 item to 4 items.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |||
| Pi | wi | 0_item | |||||||||
| 1 | 2 | 1_item | |||||||||
| 2 | 3 | 2_item | |||||||||
| 5 | 4 | 3_item | |||||||||
| 6 | 5 | 4_item | |||||||||
- If the knapsack’s capacity is 0 kg, then the entire column will show a profit of 0. Similarly, if there are no items, then the entire row will also show a profit of 0.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |||
| Pi | wi | 0_item | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 2 | 1_item | 0 | ||||||||
| 2 | 3 | 2_item | 0 | ||||||||
| 5 | 4 | 3_item | 0 | ||||||||
| 6 | 5 | 4_item | 0 | ||||||||
.
Step 1 – If the knapsack has a capacity of 1 kg and the only available item weighs 2 kg, then no items can be placed in the knapsack.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |||
| Pi | wi | 0_item | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 2 | 1_item | 0 | 0 | |||||||
| 2 | 3 | 2_item | 0 | ||||||||
| 5 | 4 | 3_item | 0 | ||||||||
| 6 | 5 | 4_item | 0 | ||||||||
.
Step 2 – If the knapsack has a capacity of 2 kg and the only available item weighs 2 kg, then that item can fit into the knapsack. The profit of this item is 1.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |||
| Pi | wi | 0_item | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 2 | 1_item | 0 | 0 | 1 | ||||||
| 2 | 3 | 2_item | 0 | ||||||||
| 5 | 4 | 3_item | 0 | ||||||||
| 6 | 5 | 4_item | 0 | ||||||||
.
Step 3 – If the knapsack’s capacity ranges from 3 kg to 8 kg and we only have one item available that fits within this capacity, with a profit of 1, then the value 1 will be entered across the remaining cells of the row.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |||
| Pi | wi | 0_item | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 2 | 1_item | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 2 | 3 | 2_item | 0 | ||||||||
| 5 | 4 | 3_item | 0 | ||||||||
| 6 | 5 | 4_item | 0 | ||||||||
.
Step 4 – From the previous row, we see that the values in the cells update to the profit of the newly added item when the item’s weight matches the knapsack’s capacity. Therefore, cells corresponding to lower weights remain unchanged.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |||
| Pi | wi | 0_item | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 2 | 1_item | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 2 | 3 | 2_item | 0 | 0 | 1 | ||||||
| 5 | 4 | 3_item | 0 | ||||||||
| 6 | 5 | 4_item | 0 | ||||||||
.
Step 5 – If the weight of the newly introduced item is 3 kg and it matches the knapsack’s capacity of 3 kg, we will include this new item if its profit is equal to or exceeds that of the previous item. Profit = 2.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |||
| Pi | wi | 0_item | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 2 | 1_item | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 2 | 3 | 2_item | 0 | 0 | 1 | 2 | |||||
| 5 | 4 | 3_item | 0 | ||||||||
| 6 | 5 | 4_item | 0 | ||||||||
.
Step 6 – With a knapsack capacity of 4 kg and a total weight of items amounting to 5 kg (2 kg for the existing item and 3 kg for the newly added item), only the newly added item will be included because it offers a higher profit.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |||
| Pi | wi | 0_item | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 2 | 1_item | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 2 | 3 | 2_item | 0 | 0 | 1 | 2 | 2 | ||||
| 5 | 4 | 3_item | 0 | ||||||||
| 6 | 5 | 4_item | 0 | ||||||||
.
Step 7 – If the knapsack capacity is 5 kg and the total weight of items amounting to 5 kg (2 kg for the existing item and 3 kg for the newly added item), then we can fit both items in the knapsack and the profit is 1 + 2 = 3.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |||
| Pi | wi | 0_item | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 2 | 1_item | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 2 | 3 | 2_item | 0 | 0 | 1 | 2 | 2 | 3 | |||
| 5 | 4 | 3_item | 0 | ||||||||
| 6 | 5 | 4_item | 0 | ||||||||
.
Step 8 – If the knapsack’s capacity ranges from 6 kg to 8 kg and we only have two item available that fits within this capacity, with a profit of 3, then the value 3 will be entered across the remaining cells of the row.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |||
| Pi | wi | 0_item | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 2 | 1_item | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 2 | 3 | 2_items | 0 | 0 | 1 | 2 | 2 | 3 | 3 | 3 | 3 |
| 5 | 4 | 3_items | 0 | ||||||||
| 6 | 5 | 4_items | 0 | ||||||||
.
Step 9 – From the previous row, we see that the values in the cells update to the profit of the newly added item when the item’s weight matches the knapsack’s capacity. Therefore, cells corresponding to lower weights remain unchanged.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |||
| Pi | wi | 0_item | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 2 | 1_item | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 2 | 3 | 2_items | 0 | 0 | 1 | 2 | 2 | 3 | 3 | 3 | 3 |
| 5 | 4 | 3_items | 0 | 0 | 1 | 2 | |||||
| 6 | 5 | 4_items | 0 | ||||||||
.
Step 10 – If the weight of the newly introduced item is 4 kg and it matches the knapsack’s capacity of 4 kg, we will include this new item if its profit is equal to or exceeds that of the previous item. Profit = 5.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |||
| Pi | wi | 0_item | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 2 | 1_item | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 2 | 3 | 2_items | 0 | 0 | 1 | 2 | 2 | 3 | 3 | 3 | 3 |
| 5 | 4 | 3_items | 0 | 0 | 1 | 2 | 5 | ||||
| 6 | 5 | 4_items | 0 | ||||||||
.
Step 11 – With a knapsack capacity of 5 kg and we have 3 items and their weights are 2, 3 and 4 kgs. So, we will fit 4 kg item because that item is having the highest profit = 5.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |||
| Pi | wi | 0_item | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 2 | 1_item | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 2 | 3 | 2_items | 0 | 0 | 1 | 2 | 2 | 3 | 3 | 3 | 3 |
| 5 | 4 | 3_items | 0 | 0 | 1 | 2 | 5 | 5 | |||
| 6 | 5 | 4_items | 0 | ||||||||
.
Step 12 – With a knapsack capacity of 6 kg, we will fit 4 kg item and 2 kg item in the knapsack, to get the highest profit = 5 + 1 = 6.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |||
| Pi | wi | 0_item | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 2 | 1_item | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 2 | 3 | 2_items | 0 | 0 | 1 | 2 | 2 | 3 | 3 | 3 | 3 |
| 5 | 4 | 3_items | 0 | 0 | 1 | 2 | 5 | 5 | 6 | ||
| 6 | 5 | 4_items | 0 | ||||||||
.
Step 13 – With the knapsack capacity of 7 kg, we will fit 4 kg item and 3 kg item in the knapsack. The profit is 2 + 5 = 7.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |||
| Pi | wi | 0_item | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 2 | 1_item | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 2 | 3 | 2_items | 0 | 0 | 1 | 2 | 2 | 3 | 3 | 3 | 3 |
| 5 | 4 | 3_items | 0 | 0 | 1 | 2 | 5 | 5 | 6 | 7 | |
| 6 | 5 | 4_items | 0 | ||||||||
.
Step 14 – We have 3 items and total weight is 2 + 3 + 4 = 9 kg. With the knapsack capacity of 8 kg, we can not fit three items. So, we will fit 4 kg and 3 kg item and the profit is 7.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |||
| Pi | wi | 0_item | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 2 | 1_item | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 2 | 3 | 2_items | 0 | 0 | 1 | 2 | 2 | 3 | 3 | 3 | 3 |
| 5 | 4 | 3_items | 0 | 0 | 1 | 2 | 5 | 5 | 6 | 7 | 7 |
| 6 | 5 | 4_items | 0 | ||||||||
.
Step 15 – From the previous row, we see that the values in the cells update to the profit of the newly added item when the item’s weight matches the knapsack’s capacity. Therefore, cells corresponding to lower weights remain unchanged.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |||
| Pi | wi | 0_item | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 2 | 1_item | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 2 | 3 | 2_items | 0 | 0 | 1 | 2 | 2 | 3 | 3 | 3 | 3 |
| 5 | 4 | 3_items | 0 | 0 | 1 | 2 | 5 | 5 | 6 | 7 | 7 |
| 6 | 5 | 4_items | 0 | 0 | 1 | 2 | 5 | ||||
.
Step 16 – If the weight of the newly introduced item is 5 kg and it matches the knapsack’s capacity of 5 kg, we will include this new item if its profit is equal to or exceeds that of the previous item. Profit = 6.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |||
| Pi | wi | 0_item | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 2 | 1_item | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 2 | 3 | 2_items | 0 | 0 | 1 | 2 | 2 | 3 | 3 | 3 | 3 |
| 5 | 4 | 3_items | 0 | 0 | 1 | 2 | 5 | 5 | 6 | 7 | 7 |
| 6 | 5 | 4_items | 0 | 0 | 1 | 2 | 5 | 6 | |||
.
Step 17 – With a knapsack capacity of 6 kg, there are two options: either select the items weighing 2 kg and 4 kg together, which give a combined profit of 6, or choose the single item weighing 5 kg, which also has a profit of 6.
If both scenarios offer the same profit, the preference would be for the option with the lesser total weight.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |||
| Pi | wi | 0_item | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 2 | 1_item | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 2 | 3 | 2_items | 0 | 0 | 1 | 2 | 2 | 3 | 3 | 3 | 3 |
| 5 | 4 | 3_items | 0 | 0 | 1 | 2 | 5 | 5 | 6 | 7 | 7 |
| 6 | 5 | 4_items | 0 | 0 | 1 | 2 | 5 | 6 | 6 | ||
.
Step 18 – With a knapsack capacity of 7 kg, we choose 5 kg item and 2 kg item with a profit of 1 + 6 = 7.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |||
| Pi | wi | 0_item | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 2 | 1_item | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 2 | 3 | 2_items | 0 | 0 | 1 | 2 | 2 | 3 | 3 | 3 | 3 |
| 5 | 4 | 3_items | 0 | 0 | 1 | 2 | 5 | 5 | 6 | 7 | 7 |
| 6 | 5 | 4_items | 0 | 0 | 1 | 2 | 5 | 6 | 6 | 7 | |
.
Step 19 – With a knapsack capacity of 8 kg, we choose 5 kg item and 3 kg item, with a profit of 6 + 2 = 8.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |||
| Pi | wi | 0_item | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 2 | 1_item | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 2 | 3 | 2_items | 0 | 0 | 1 | 2 | 2 | 3 | 3 | 3 | 3 |
| 5 | 4 | 3_items | 0 | 0 | 1 | 2 | 5 | 5 | 6 | 7 | 7 |
| 6 | 5 | 4_items | 0 | 0 | 1 | 2 | 5 | 6 | 6 | 7 | 8 |
.
The maximum value that can be achieved with all items and a weight limit of 8 kg is profit = 8. This is your solution, indicating the maximum profit achievable under the given constraints.
The table will fill the same if we use the algorithm formula.
dp[i][j] = max(dp[i-1][j], dp[i-1][j-wi] + pi)
Knapsack Backtracking Item Selection
Everyone is interested in finding out whether the maximum profit of 8 comes from including the 2nd and 4th items in the knapsack, or if it comes from including the 1st, 2nd, and 3rd items instead.
So, we will apply backtracking.
.
Algorithm of Backtracking
- Start from the last cell of last row of the dynamic programming table.
- If the value in the current cell is the same as the value in the cell above it, move to the cell above.
- Else If the value in the current cell is greater than the value in the cell above it, mark the corresponding item as included and subtract the profit of the corresponding item into current cell’s value.
- Reach on the new value by backtracking (going backwards).
- Repeat steps 2, 3 and 4 until you reach the first row of the table or the capacity becomes 0.
- The items marked as included are the ones to be taken to maximize the profit within the given capacity.
.
We have to represent (item 1, item 2, item 3, item 4) in 0 and 1 form.
With the backtracking algorithm, we look the last cell of the last row (Brown row). The cell’s value is 8, and above cell’s value is 7. It is less than the value 8, so 4th item is included in the knapsack.
After that, we subtract 6 from 8 as 6 is the profit of 4th item.
We get the value 2 and after going backwards (backtracking) we found this value in 3rd row (Red row) and knapsack capacity 3 kg column.
The value in the above cell is 2 (Yellow row), so 3rd item is not included in the knapsack.
Again, the same instruction given by the algorithm. The above cell is 1 (Green row). So, 2nd item is included in the knapsack.
After that, we subtract 2 from 2 as 2 is the profit of 2nd item.
We get the value 0 and after going backwards (backtracking) we found this value in 1st row (Green row) and knapsack capacity 1 kg column.
The value in the above cell is 0 (Blue row), so 1st item is not included in the knapsack.
The items (item 1, item 2, item 3, item 4) included in the knapsack are (0, 1, 0, 1).
.
Source Code of 0/1 Knapsack Problem
// COMPUTER GEEK – compgeek.co.in
// Write a program for 0/1 Knapsack Problem
#include <stdio.h>
#include <stdlib.h>
int max(int a, int b) {
return (a > b) ? a : b;
}
int knapsack(int W, int wt[], int val[], int n) {
int i, w;
int **dp = (int**) malloc((n+1) * sizeof(int*));
for (i = 0; i <= n; i++) {
dp[i] = (int*) malloc((W+1) * sizeof(int));
}
// Build table dp[][] in a bottom up manner
for (i = 0; i <= n; i++) {
for (w = 0; w <= W; w++) {
if (i == 0 || w == 0)
dp[i][w] = 0;
else if (wt[i-1] <= w)
dp[i][w] = max(val[i-1] + dp[i-1][w-wt[i-1]], dp[i-1][w]);
else
dp[i][w] = dp[i-1][w];
}
}
// Store the result and free memory
int result = dp[n][W];
for (i = 0; i <= n; i++) {
free(dp[i]);
}
free(dp);
return result;
}
int main() {
int n, W, i;
printf(“Enter the number of items: “);
scanf(“%d”, &n);
printf(“Enter the capacity of knapsack: “);
scanf(“%d”, &W);
int *wt = (int*) malloc(n * sizeof(int));
int *val = (int*) malloc(n * sizeof(int));
for (i = 0; i < n; i++) {
printf(“Enter weight and profit for item %d: “, i + 1);
scanf(“%d %d”, &wt[i], &val[i]);
}
printf(“Maximum profit: %d\n”, knapsack(W, wt, val, n));
free(wt);
free(val);
return 0;
}
// COMPUTER GEEK – compgeek.co.in
// Write a program for 0/1 Knapsack Problem
#include <iostream>
#include <vector>
using namespace std;
int knapsack(int W, vector<int>& wt, vector<int>& val, int n) {
vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));
for (int i = 1; i <= n; i++) {
for (int w = 0; w <= W; w++) {
if (wt[i – 1] <= w)
dp[i][w] = max(dp[i – 1][w], dp[i – 1][w – wt[i – 1]] + val[i – 1]);
else
dp[i][w] = dp[i – 1][w];
}
}
return dp[n][W];
}
int main() {
int n, W;
cout << “Enter the number of items: “;
cin >> n;
cout << “Enter the capacity of knapsack: “;
cin >> W;
vector<int> wt(n), val(n);
for (int i = 0; i < n; i++) {
cout << “Enter weight and profit for item ” << i + 1 << “: “;
cin >> wt[i] >> val[i];
}
cout << “Maximum profit: ” << knapsack(W, wt, val, n) << endl;
return 0;
}
// COMPUTER GEEK – compgeek.co.in
// Write a program for 0/1 Knapsack Problem
import java.util.Scanner;
public class Knapsack {
public static int knapsack(int W, int[] wt, int[] val, int n) {
int[][] dp = new int[n + 1][W + 1];
for (int i = 1; i <= n; i++) {
for (int w = 0; w <= W; w++) {
if (wt[i – 1] <= w)
dp[i][w] = Math.max(dp[i – 1][w], dp[i – 1][w – wt[i – 1]] + val[i – 1]);
else
dp[i][w] = dp[i – 1][w];
}
}
return dp[n][W];
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.print(“Enter the number of items: “);
int n = scanner.nextInt();
System.out.print(“Enter the capacity of knapsack: “);
int W = scanner.nextInt();
int[] wt = new int[n];
int[] val = new int[n];
for (int i = 0; i < n; i++) {
System.out.print(“Enter weight and profit for item ” + (i + 1) + “: “);
wt[i] = scanner.nextInt();
val[i] = scanner.nextInt();
}
System.out.println(“Maximum profit: ” + knapsack(W, wt, val, n));
scanner.close();
}
}
# COMPUTER GEEK – compgeek.co.in
# Write a program for 0/1 Knapsack Problem
def knapsack(W, wt, val, n):
dp = [[0 for x in range(W + 1)] for x in range(n + 1)]
for i in range(1, n + 1):
for w in range(W + 1):
if wt[i – 1] <= w:
dp[i][w] = max(dp[i – 1][w], dp[i – 1][w – wt[i – 1]] + val[i – 1])
else:
dp[i][w] = dp[i – 1][w]
return dp[n][W]
def main():
n = int(input(“Enter the number of items: “))
W = int(input(“Enter the capacity of knapsack: “))
wt = []
val = []
for i in range(n):
print(“Enter weight and profit for item {}: “.format(i + 1), end=”)
inputs = input().split()
wt.append(int(inputs[0]))
val.append(int(inputs[1]))
print(“Maximum profit:”, knapsack(W, wt, val, n))
if __name__ == “__main__”:
main()
Enter the number of items: 4
Enter the capacity of knapsack: 8
Enter weight and profit for item 1: 2 1
Enter weight and profit for item 2: 3 2
Enter weight and profit for item 3: 4 5
Enter weight and profit for item 4: 5 6
Maximum profit: 8
=== Code Execution Successful ===
Time Complexity
- Initializing Table – Initializing the table requires 𝑂(𝑛×𝑊) time because it involves filling up a 2D array with 𝑛+1 rows and 𝑊+1 columns.
- Filling DP Table – Filling up the DP table involves a nested loop. The outer loop runs for 𝑛 iterations (for each item), and the inner loop runs for 𝑊 iterations (for each weight capacity). So, the time complexity for filling the table is also 𝑂(𝑛×𝑊).
- Retrieving Maximum Profit: Once the DP table is filled, retrieving the maximum profit is a constant time operation.
.
Space Complexity
The space complexity of the 0/1 Knapsack problem solution implemented using dynamic programming, as described in the provided algorithms, is 𝑂(𝑛×𝑊) where 𝑛 is the number of items and 𝑊 is the capacity of the knapsack.
.
Application
- Resource Allocation – Optimizes the selection of projects or investments with constrained capital.
- Data Compression – Used in methodologies where selecting parts of data for the most efficient compression is required.
- Resource Scheduling – Optimizes the allocation of limited resources like CPUs or network bandwidth to tasks.
- Backpack Loading for Hiking – Helps in selecting the most necessary and valuable items to carry within weight capacity for optimal hiking experience.
- Cutting Stock Problem – Minimizes waste while cutting raw materials into smaller sizes based on demand.
Test Yourself
Q1- Difference between greedy algorithm vs dynamic programming.
Aspect | Greedy Algorithm | Dynamic Programming |
Principle | Makes a locally optimal choice at each step with the hope of finding a global optimum. | Solves problems by combining the solutions to subproblems. |
Optimality | Does not always yield a globally optimal solution; only optimal in problems with greedy-choice property. | Guaranteed to reach an optimal solution by considering all possible configurations. |
Approach | Builds up a solution piece by piece, choosing the next piece that offers the most immediate benefit. | Breaks down the problem into smaller subproblems and solves each one only once, storing the results for future use (memoization or tabulation). |
Subproblem Overlap | No subproblem overlap; once a decision is made, it is not revisited. | Subproblems overlap; solutions to subproblems are reused. |
Problem Type Suitability | Best for problems where local optimal choices lead to a global optimum, such as Huffman coding, or Prim’s and Kruskal’s algorithms for Minimum Spanning Tree. | Suitable for problems with overlapping subproblems and optimal substructure, like the 0/1 Knapsack problem, and computing Fibonacci numbers. |
Memory Usage | Generally uses less memory as it does not store results of subproblems. | Uses more memory to store the results of subproblems, unless optimized using space-efficient techniques. |
Performance | Often faster, because it only computes the necessary parts of the solution without reconsidering previous decisions. | Can be slower due to the thorough approach of exploring multiple possible solutions and storing subproblem results. |
Example Problems | Fractional Knapsack, Activity Selection Problem. | 0/1 Knapsack Problem, Bellman-Ford Algorithm, Shortest Path problems, Matrix Chain Multiplication. |
Solution Revision | Does not go back to change decisions. | May revisit and revise decisions based on later discoveries (via stored values). |
Complexity Management | Tends to have simpler implementations but can struggle with problems requiring global considerations. | Handles complex dependencies and constraints more effectively, especially when exhaustive consideration is required. |
Q2- Can the knapsack problem be solved faster if all weights are equal but only the values differ?
Always pick items with the highest values first until the knapsack is full or no more items can fit.
Q3- Can the knapsack problem be solved faster if all weights are equal but only the values differ?
Yes, you can simply sort items by their values in descending order and pick the top items until the capacity is reached. Also, time complexity will decrease as knapsack does not require a dynamic table approach.
Q4- In dynamic programming, how does the problem change if item weights are fractions?
If weights are fractions, you are no longer dealing with the 0/1 Knapsack problem but with the fractional knapsack problem, which can be solved using a greedy approach.
Q5- What happens if two items have the same value-to-weight ratio in dynamic programming?
If their ratios are the same, you can choose either item. However, practical implementation might pick the one that appears first in the list unless otherwise optimized.
Q6- Is it possible for a smaller capacity knapsack to have a higher maximum value than a larger capacity?
No, as increasing the capacity does not decrease the maximum value achievable; it either stays the same or increases.
Example – if you have three items. Item 1 is of 3 kg, item 2 is of 5 kg and item 3 is of 7 kg. Now you have two knapsacks, one is of the capacity 3 kg and second is of the capacity of 4 kg, then in both the knapsack only item 1 will fit. Profit remains same.
Q7- Can dynamic programming solve the 0/1 Knapsack problem in linear time?
No, the dynamic programming solution to the 0/1 Knapsack problem runs in O(nW), which is pseudo-polynomial and not linear time.
Q8- What is the time complexity of the brute-force solution to the 0/1 Knapsack problem?
1. O(n)
2. O(W)
3. O(nW)
4. O(2n)
Ans – (4)
Explanation – The brute-force solution considers all subsets of the items, resulting in 2n possible combinations.
If there are n items to be placed in the knapsack, then there are 2n possible combinations.
Q9- What is the key property of the 0/1 Knapsack problem that allows it to be solved using dynamic programming?
1. Overlapping subproblems
2. Non-overlapping subproblems
3. Lack of optimal substructure
4. Increasing order of items
Ans – (1)
Explanation – Dynamic programming is applicable because of overlapping subproblems and optimal substructure properties.
Q10- What is NP-complete status of the 0/1 Knapsack problem indicating?
1. The problem cannot be solved in polynomial time
2. The problem can be solved in logarithmic time
3. No solution exists for the problem
4. The problem is not suitable for computers
Ans – (1)
Explanation – NP-completeness indicates that there is no known polynomial-time algorithm to solve all cases of the problem optimally.
Q11- Which of the following is not a direct application of the 0/1 Knapsack problem?
1. Selecting stocks for investment within a budget
2. Choosing the least valuable items to fit in a bag
3. Allocating CPUs to processes to maximize performance
4. Packing the most valuable items in a limited space suitcase
Ans – (2)
Explanation – The 0/1 Knapsack problem focuses on maximizing value, not minimizing it.
