DevJourney · code I wrote while learning

README.md

1.2 KB

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

  1. Read the number of items n and knapsack capacity W.
  2. Read the weights and values of the items.
  3. Initialize the DP table using base conditions.
  4. Fill the DP table using the recurrence relation.
  5. 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.