🎒 Knapsack Problem – Complete In-Depth Explanation

The **Knapsack Problem** is a fundamental **optimization problem** in **computer science** and **mathematics**. It involves selecting items to place in a **knapsack (bag)** to maximize the **total value**, while ensuring that the total weight does not exceed a given limit.

📌 Types of Knapsack Problems

The Knapsack problem can be categorized into **three main types**:

  • 📦 **0/1 Knapsack Problem** – Items cannot be divided; you either take the entire item or leave it.
  • 📉 **Fractional Knapsack Problem** – Items can be divided; you can take fractions of an item.
  • 🔄 **Unbounded Knapsack Problem** – An unlimited supply of each item is available.

📌 Understanding the 0/1 Knapsack Problem

Given a set of **N items**, each with a **weight** and **value**, and a knapsack that can carry a maximum **weight W**, determine the **maximum value** that can be obtained by selecting a subset of the items.

🔹 **Mathematical Formulation**

Let:

  • 📦 **N** = Total number of items.
  • ⚖️ **W** = Maximum weight the knapsack can hold.
  • 📊 **w[i]** = Weight of the i-th item.
  • 💰 **v[i]** = Value of the i-th item.
  • 📝 **x[i]** = 1 if item is included, 0 otherwise.

We need to maximize:


                Maximize: Σ (x[i] * v[i])  for  i = 1 to N
                Subject to: Σ (x[i] * w[i]) ≤ W  for  i = 1 to N

🛠 Solution Methods for 0/1 Knapsack

📌 **1. Recursion (Brute Force) – O(2^N) Complexity**

A **recursive solution** that checks both possibilities: **including** or **excluding** an item. 


                int knapsack(int W, vector& weight, vector& value, int n) {
                    if (n == 0 || W == 0) return 0;
            
                    if (weight[n - 1] > W)
                        return knapsack(W, weight, value, n - 1);
            
                    return max(value[n - 1] + knapsack(W - weight[n - 1], weight, value, n - 1),
                               knapsack(W, weight, value, n - 1));
                }

🔴 **Disadvantage:** Exponential complexity **O(2^N)** is inefficient for large N.

📌 **2. Dynamic Programming (O(N × W) Complexity)**

Instead of **recomputing solutions**, we **store** results in a **table (memoization)** and use them to avoid redundant calculations.

🔹 **Bottom-Up Approach (Tabulation Method)**


                int knapsackDP(int W, vector& weight, vector& value, int N) {
                    vector> dp(N + 1, vector(W + 1, 0));
            
                    for (int i = 1; i <= N; i++) {
                        for (int w = 0; w <= W; w++) {
                            if (weight[i - 1] <= w) {
                                dp[i][w] = max(value[i - 1] + dp[i - 1][w - weight[i - 1]], dp[i - 1][w]);
                            } else {
                                dp[i][w] = dp[i - 1][w];
                            }
                        }
                    }
                    return dp[N][W];
                }

📌 **3. Space Optimized DP (O(W) Complexity)**

Instead of a **2D table**, we use a **1D array**, updating it from **right to left**. 


                int knapsackOptimized(int W, vector& weight, vector& value, int N) {
                    vector dp(W + 1, 0);
            
                    for (int i = 0; i < N; i++) {
                        for (int w = W; w >= weight[i]; w--) {
                            dp[w] = max(dp[w], value[i] + dp[w - weight[i]]);
                        }
                    }
                    return dp[W];
                }

📌 Fractional Knapsack (O(N log N))

Unlike **0/1 Knapsack**, here we can take **fractions** of items.

🔹 **Greedy Strategy:**

  • ✅ Sort items by **value/weight ratio**.
  • 🔄 Take **whole items** first.
  • 📉 If the knapsack is full, take **a fraction** of the next item.

                struct Item {
                    int weight, value;
                };
            
                bool cmp(Item a, Item b) {
                    return (double)a.value / a.weight > (double)b.value / b.weight;
                }
            
                double fractionalKnapsack(int W, vector& items) {
                    sort(items.begin(), items.end(), cmp);
                    double maxValue = 0.0;
            
                    for (auto item : items) {
                        if (W >= item.weight) {
                            maxValue += item.value;
                            W -= item.weight;
                        } else {
                            maxValue += item.value * ((double)W / item.weight);
                            break;
                        }
                    }
                    return maxValue;
                }

⏳ Time Complexity Analysis

Algorithm Time Complexity
Recursive (Brute Force) O(2^N)
Dynamic Programming (2D DP) O(N × W)
Space Optimized DP (1D DP) O(N × W)
Fractional Knapsack (Greedy) O(N log N)

🌍 Real-World Applications of Knapsack Problem

  • 📡 **Resource Allocation** – Distributing resources efficiently.
  • 🎮 **Game Inventory Management** – Selecting the best combination of items.
  • 🛒 **Budget Optimization** – Choosing the best products within a budget.
  • 📈 **Stock Market Analysis** – Portfolio selection for maximum returns.

🔗 Next Topics