---

📘 Knapsack Problem

1️⃣ Introduction

The Knapsack Problem is a classical optimization problem in computer science and operations research.

It focuses on selecting items in such a way that:

• Total profit is maximized
• Total weight does not exceed capacity

The problem is widely used to explain Greedy Method, Dynamic Programming, and NP-Complete concepts.

---

2️⃣ Problem Statement

Given:

• n items
• Each item i has:
  • Weight wᵢ
  • Profit (value) pᵢ
• A knapsack with capacity W

Objective:

Select a subset of items such that
🔹 Total weight ≤ W
🔹 Total profit is maximum

---

3️⃣ Types of Knapsack Problem

🔹 1. Fractional Knapsack

• Items can be broken into fractions
• Solved using Greedy Approach

🔹 2. 0/1 Knapsack

• Items are indivisible
• Either take the item (1) or leave it (0)
• Solved using Dynamic Programming

---

4️⃣ Fractional Knapsack Problem

🔹 Key Idea

• Select items based on profit/weight ratio
• Pick the item with highest value density first

🔹 Algorithm (Greedy)

1. Calculate pᵢ / wᵢ for each item
2. Sort items in descending order
3. Add items fully or partially until capacity is filled

---

🔹 Example

Items:

Item	Weight	Profit	p/w
A	10	60	6
B	20	100	5
C	30	120	4

Knapsack Capacity = 50

✔ Take A + B fully
✔ Take 2/3 of C

Maximum Profit = 240

---

🔹 Time Complexity

• O(n log n) (sorting)

---

5️⃣ 0/1 Knapsack Problem

🔹 Key Idea

• Each item can be taken only once
• Greedy approach does not work
• Solved using Dynamic Programming

---

6️⃣ Dynamic Programming Solution (0/1 Knapsack)

🔹 DP Table

Let:

dp[i][w] = maximum profit using first i items and capacity w

---

🔹 Recurrence Relation

[
dp[i][w] =
\begin{cases}
dp[i-1][w] & \text{if } w_i > w \
\max(dp[i-1][w],; p_i + dp[i-1][w-w_i]) & \text{if } w_i \le w
\end{cases}
]

---

🔹 Algorithm Steps

1. Create DP table of size (n+1) × (W+1)
2. Fill table row by row
3. Final answer = dp[n][W]

---

🔹 Time & Space Complexity

• Time Complexity: O(nW)
• Space Complexity: O(nW)

---

7️⃣ Comparison: Fractional vs 0/1 Knapsack

Feature	Fractional	0/1
Item division	Allowed	Not allowed
Technique	Greedy	Dynamic Programming
Optimal solution	Guaranteed	Guaranteed
Complexity	O(n log n)	O(nW)
Nature	Polynomial	NP-Complete

---

8️⃣ Applications of Knapsack Problem

• Resource allocation
• Budget management
• Cargo loading
• Investment selection
• Cryptography
• Scheduling problems

---

9️⃣ Advantages and Limitations

✔ Advantages

• Models real-life optimization problems
• Demonstrates DP and Greedy techniques
• Guarantees optimal solution (DP)

✖ Limitations

• High memory usage (DP)
• Large W makes DP impractical
• NP-Complete (0/1 version)

---

🔚 Conclusion

The Knapsack Problem is a fundamental optimization problem that demonstrates how algorithm design techniques vary based on constraints.

Fractional Knapsack is solved greedily, while 0/1 Knapsack requires Dynamic Programming for optimal results.

---