Knapsack Problem
Knapsack Problem एक classic optimization problem है, जिसमें हमें कुछ items दिए जाते हैं, जिनमें हर item का weight और value होती है। हमें select करना होता है कुछ items इस तरह कि total value maximize हो और total weight limit (capacity of knapsack) से ज्यादा न हो।
Mathematically :
- Given :
- n items
- Each item has weight wiऔर value vi
- Knapsack capacity = W
- Find : Maximum total value such that
Key Points
- हर item का weight (wi) और value (vi) होता है।
- Knapsack की capacity = W होती है।
- Greedy, Dynamic Programming, और Backtracking approaches से solve किया जाता है।
- Types :
- 0/1 Knapsack
- Fractional Knapsack
Types of Knapsack Problem (प्रकार)
Knapsack Problem मुख्य रूप से दो major types में classified है। इन दोनों के लिए problem-solving techniques अलग होती हैं।
- 0/1 Knapsack Problem
- Fractional Knapsack Problem
1. 0/1 Knapsack Problem
0/1 Knapsack Problem एक optimization problem है, जिसमें हमें n items दिए जाते हैं।
- हर item का weight (wᵢ) और value (vᵢ) होता है।
- Knapsack की capacity W होती है।
Goal :
- Total value maximize हो
- Total weight ≤ W
Example
| Item | Weight (w) | Value (v) |
|---|---|---|
| 1 | 1 | 10 |
| 2 | 3 | 40 |
| 3 | 4 | 50 |
| 4 | 5 | 70 |
Knapsack Capacity (W) = 7
Step 1: Initialize DP Table
- Create a table dp[n+1][W+1] where n = 4, W = 7
- Rows = items + 1 = 5
- Columns = capacity + 1 = 8
- Initialize first row and first column with 0
| i\w | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | |||||||
| 2 | 0 | |||||||
| 3 | 0 | |||||||
| 4 | 0 |
Step 2: Fill DP Table (Item by Item)
Item 1 (w=1, v=10)
- For each capacity w from 1 to 7
- If weight ≤ w, dp[i] [w] = max(dp[i-1] [w], value + dp[i-1] [w-weight])
- Here, dp[1] [1] = 10, dp[1] [2] = 10 … dp[1] [7] = 10
| i\w | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| 1 | 0 | 10 | 10 | 10 | 10 | 10 | 10 | 10 |
Item 2 (w=3, v=40)
- dp[2] [1] = 10 (weight > capacity? no, weight > 1? yes → dp[i-1] [w])
- dp[2] [2] = 10
- dp[2] [3] = max(dp[1] [3], v2 + dp[1] [3-3]) = max(10, 40+0) = 40
- dp[2] [4] = max(dp[1] [4], 40 + dp[1] [4-3]) = max(10, 40+10) = 50
- dp[2] [5] = max(10, 40+10) = 50
- dp[2] [6] = max(10, 40+10) = 50
dp[2] [7] = max(10, 40+10) = 50
| i\w | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| 2 | 0 | 10 | 10 | 40 | 50 | 50 | 50 | 50 |
Item 3 (w = 4, v = 50)
- dp[3] [1] = 10
- dp[3] [2] = 10
- dp[3] [3] = 40
- dp[3] [4] = max(50, 50 + 0) = 50
- dp[3] [5] = max(50, 50 + 10) = 60
- dp[3] [6] = max(50, 50 + 10) = 60
- dp[3] [7] = max(50, 50 + 40) = 90
| i\w | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| 3 | 0 | 10 | 10 | 40 | 50 | 60 | 60 | 90 |
Item 4 (w = 5, v = 70)
- dp[4] [1] = 10
- dp[4] [2] = 10
- dp[4] [3] = 40
- dp[4] [4] = 50
- dp[4] [5] = max(50, 70 + 0) = 70
- dp[4] [6] = max(60, 70 + 10) = 80
- dp[4] [7] = max(90, 70 + 40) = 110
| i\w | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| 4 | 0 | 10 | 10 | 40 | 50 | 70 | 80 | 110 |
Step 3: Maximum Value
Maximum value = dp[4] [7] = 110
Step 4: Traceback (Selected Items)
- Start from dp[4] [7] = 110
- dp[4] [7] ≠ dp[3] [7] → Item 4 included
- Remaining weight = 7 – 5 = 2 → look at dp[3] [2]
- dp[3] [2] = 10 ≠ dp[2] [2] → Item 1 included
Selected Items: Item 1 + Item 4
- Total weight = 1 + 5 = 6 ≤ 7
- Total value = 10 + 100 = 110
Pseudo Code
Input: n items, weight w[], value v[], capacity W
Output: Maximum value
1. Create dp[n+1][W+1]
2. Initialize dp[0][w] = 0 and dp[i][0] = 0
3. For i = 1 to n:
For w = 1 to W:
if w[i] <= w:
dp[i][w] = max(dp[i-1][w], v[i] + dp[i-1][w – w[i]])
else:
dp[i][w] = dp[i-1][w]
4. Return dp[n][W]
Advantages of 0/1 Knapsack Problem
- Exact / Optimal Solution : 0/1 Knapsack Problem हमेशा best possible (optimal) solution देता है, जिसमें maximum value के साथ सही items select होते हैं।
- Lossless Selection : इस problem में हर item या तो पूरी तरह select होता है या पूरी तरह reject, इसलिए value का कोई loss नहीं होता।
- Dynamic Programming Example : यह problem Dynamic Programming (DP) concept को समझने के लिए एक बहुत अच्छा और standard example है।
- Real-Life Applications : 0/1 Knapsack का use budget planning, resource allocation, project selection जैसी real-world problems में किया जाता है।
- Clear Decision Making : Binary decision (0 या 1) होने की वजह से decision-making process आसान और clear रहता है।
Disadvantages of 0/1 Knapsack Problem
- High Time Complexity : DP approach की time complexity O(n × W) होती है, जो बड़े input size के लिए slow हो सकती है।
- Large Memory Requirement : DP table बनाने के लिए ज्यादा memory (space complexity) की जरूरत होती है।
- No Fraction Allowed : इस problem में items को fraction में select नहीं किया जा सकता, जबकि कई real-life situations में partial selection possible होती है।
- Not Suitable for Large Capacity (W) : अगर knapsack की capacity बहुत ज्यादा हो, तो यह problem practically inefficient हो जाती है।
- Pseudo-Polynomial Algorithm : यह algorithm truly polynomial नहीं है क्योंकि इसकी complexity capacity W पर depend करती है, न कि सिर्फ input size पर।
2. Fractional Knapsack Problem
Fractional Knapsack Problem एक optimization problem है, जिसमें हमें कुछ items दिए जाते हैं।
हर item का weight और value होता है, तथा knapsack की एक fixed capacity होती है।
Goal : Items को पूरी तरह या fraction (भागों में) इस तरह select करना कि
- Total value maximum हो
- Total weight knapsack capacity से ज्यादा न हो
Example
Given Items
| Item | Weight (w) | Value (v) |
|---|---|---|
| A | 10 | 60 |
| B | 20 | 100 |
| C | 30 | 120 |
Knapsack Capacity (W) = 50
Step 1: Calculate Value / Weight Ratio
| Item | Weight | Value | Value/Weight |
|---|---|---|---|
| A | 10 | 60 | 6 |
| B | 20 | 100 | 5 |
| C | 30 | 120 | 4 |
Step 2: Sort Items (Descending Order of Ratio)
Order will be :
A → B → C
Step 3: Start Filling the Knapsack
1. Item A
- Weight = 10 ≤ 50
- Take 100% of A
- Remaining capacity = 50 − 10 = 40
- Total value = 60
2. Item B
- Weight = 20 ≤ 40
- Take 100% of B
- Remaining capacity = 40 − 20 = 20
- Total value = 60 + 100 = 160
3. Item C
- Weight = 30 > 20
- Take fraction of C
Fraction taken = 20 / 30 = 2/3
Value added = 120 × (2/3) = 80
Step 4: Final Answer
- Total weight used = 50
- Maximum value obtained = 160 + 80 = 240
Pseudocode
Fractional_Knapsack(W, weight[], value[], n)
1. For each item i = 1 to n
calculate ratio[i] = value[i] / weight[i]
2. Sort all items in decreasing order of ratio[]
3. totalValue = 0
4. For i = 1 to n
if weight[i] ≤ W then
W = W – weight[i]
totalValue = totalValue + value[i]
else
fraction = W / weight[i]
totalValue = totalValue + (value[i] * fraction)
break
5. Return totalValue
Advantages of Fractional Knapsack Problem
- Optimal Solution : Greedy Algorithm के use की वजह से Fractional Knapsack Problem हमेशा maximum possible value का optimal solution देता है।
- Fraction Allowed : इस problem में items को partial (fraction में) लिया जा सकता है, जो कई real-life situations में ज्यादा practical होता है।
- Low Time Complexity : Fractional Knapsack की time complexity O(n log n) होती है, इसलिए यह large inputs के लिए efficient है।
- Simple Algorithm : Greedy approach होने के कारण algorithm समझने और implement करने में आसान होता है।
- Real-World Applications : यह problem gold, oil, grains, investment planning, cargo loading जैसी divisible items वाली situations में use होती है।
Disadvantages of Fractional Knapsack Problem
- Not Suitable for Indivisible Items : जहाँ items को तोड़ा या divide नहीं किया जा सकता, वहाँ Fractional Knapsack apply नहीं होता।
- Not Valid for 0/1 Knapsack : Binary decision (0 या 1) वाली problems में Greedy approach सही result नहीं देता।
- Sorting Required : Items को value/weight ratio के according sort करना पड़ता है, जिससे extra computation लगता है।
- Limited Practical Use : हर real-world problem में items को fraction में select करना possible नहीं होता।
- Conceptually Misleading : कुछ problems में partial selection realistic नहीं होती, फिर भी algorithm fraction allow करता है, जिससे confusion हो सकता है।
