0/1 Knapsack using Dynamic Programming
Problem Statement
Given n items, each having a weight and a value, and a knapsack of capacity W, determine the maximum total value that can be obtained by selecting items such that the total weight does not exceed W. Each item can be chosen at most once.
Technique Used
Dynamic Programming
DP Definition
dp[i][w] = Maximum value obtained using first i items with knapsack capacity w
Recurrence Relation
If the current item can be included:
dp[i][w] = max(
dp[i-1][w],
value[i-1] + dp[i-1]w - weight[i-1]]
)
If the current item cannot be included:
dp[i][w] = dp[i-1][w]
Base Conditions
dp[0][w] = 0 // No items
dp[i][0] = 0 // Zero capacity
Algorithm
- Read the number of items
nand knapsack capacityW. - Read the weights and values of the items.
- Initialize the DP table using base conditions.
- Fill the DP table using the recurrence relation.
- The final answer is stored in
dp[n][W].
Time and Space Complexity
- Time Complexity:
O(n × W) - Space Complexity:
O(n × W)
Output
Displays the maximum value that can be stored in the knapsack.