13. 0-1 Knapsack Problem

The problem can be found at the following link: Question Link

Problem Description

Given n items, each with a weight and value, and a knapsack with a capacity of W, the task is to determine the maximum total value that can be obtained by placing items in the knapsack without exceeding its weight capacity.

🔹 Note:

• Each item can be either included or excluded (hence, 0-1 Knapsack).

• Each item is available only once.

Examples

Example 1:

Input:

W = 4
val[] = [1, 2, 3]
wt[] = [4, 5, 1]

Output:

3

Explanation:

Choose the last item (value = 3, weight = 1), as it fits within the weight limit and maximizes the value.

Example 2:

Input:

W = 3
val[] = [1, 2, 3]
wt[] = [4, 5, 6]

Output:

0

Explanation:

No item fits within the weight limit W = 3, so the maximum value obtained is 0.

Example 3:

Input:

W = 5
val[] = [10, 40, 30, 50]
wt[] = [5, 4, 2, 3]

Output:

80

Explanation:

• Select the third item (value = 30, weight = 2).

• Select the fourth item (value = 50, weight = 3).

• Total weight = 2 + 3 = 5 (within limit).

• Total value = 30 + 50 = 80.

Constraints:

• $2 \leq \text{val.size()} = \text{wt.size()} \leq 10^3$

• $1 \leq W \leq 10^3$

• $1 \leq \text{val}[i] \leq 10^3$

• $1 \leq \text{wt}[i] \leq 10^3$

My Approach:

Optimized Space Dynamic Programming

Algorithm Steps:

1. Use a 1D DP array (dp[W+1]) to track the maximum value at each capacity from 0 to W.

2. Iterate over each item and update the DP array backwards (from W to wt[i]), ensuring each item is used only once.

3. For each weight j, decide whether to:

   • Include the current item: dp[j] = max(dp[j], val[i] + dp[j - wt[i]]).

   • Exclude the current item (keep previous value).

4. Return dp[W], which contains the maximum value achievable with capacity W.

Time and Auxiliary Space Complexity

• Expected Time Complexity: O(N * W), as we process N items and iterate over W capacities.

• Expected Auxiliary Space Complexity: O(W), as we use a 1D DP array of size W+1.

Code (C++)

class Solution {
  public:
    int knapsack(int W, vector<int> &val, vector<int> &wt) {
        vector<int> dp(W + 1);
        for (int i = 0; i < wt.size(); i++)
            for (int j = W; j >= wt[i]; j--)
                dp[j] = max(dp[j], val[i] + dp[j - wt[i]]);
        return dp[W];
    }
};

⚡ Alternative Approaches

1️⃣ Dynamic Programming (O(N _ W) Time, O(N _ W) Space) — Tabulation

Approach:

• Use a 2D DP table (dp[n+1][W+1]), where dp[i][j] represents the maximum value possible using the first i items with capacity j.

• Iterate over each item and capacity, making a choice to either include or exclude the current item.

class Solution {
  public:
    int knapsack(int W, vector<int> &val, vector<int> &wt) {
        int n = wt.size();
        vector<vector<int>> dp(n + 1, vector<int>(W + 1));

        for (int i = 1; i <= n; i++)
            for (int j = 0; j <= W; j++)
                dp[i][j] = (wt[i - 1] <= j)
                           ? max(dp[i - 1][j], val[i - 1] + dp[i - 1][j - wt[i - 1]])
                           : dp[i - 1][j];

        return dp[n][W];
    }
};

✅ Time Complexity: O(N * W) ✅ Space Complexity: O(N * W)

2️⃣ Recursive + Memoization (O(N _ W) Time, O(N _ W) Space)

Approach:

• Recursively try including or excluding each item, storing results in a memoization table to avoid recomputation.

• Base case: If no items remain or capacity reaches 0, return 0.

class Solution {
  public:
    vector<vector<int>> dp;
    int solve(vector<int> &val, vector<int> &wt, int i, int W) {
        if (i < 0 || W == 0) return 0;
        if (dp[i][W] != -1) return dp[i][W];

        int pick = (wt[i] <= W) ? val[i] + solve(val, wt, i - 1, W - wt[i]) : 0;
        int notPick = solve(val, wt, i - 1, W);

        return dp[i][W] = max(pick, notPick);
    }

    int knapsack(int W, vector<int> &val, vector<int> &wt) {
        dp.assign(wt.size(), vector<int>(W + 1, -1));
        return solve(val, wt, wt.size() - 1, W);
    }
};

✅ Time Complexity: O(N * W) ✅ Space Complexity: O(N * W)

🔍 Comparison of Approaches

Approach	⏱️ Time Complexity	🗂️ Space Complexity	✅ Pros	⚠️ Cons
Iterative DP (Space Optimized)	🟡 O(N * W)	🟢 O(W)	Fastest and most optimized	Requires iterative logic
Dynamic Programming (Tabulation)	🟡 O(N * W)	🔴 O(N * W)	Easy to understand	High space complexity
Recursive + Memoization	🟡 O(N * W)	🔴 O(N * W)	Natural recursive logic	High recursion overhead

💡 Best Choice?

✅ For simplicity and efficiency: Use Iterative DP (Space Optimized). ✅ For understanding step-by-step execution: Use Tabulation DP. ✅ For recursion lovers: Use Memoization DP.

Code (Java)

class Solution {
    static int knapsack(int W, int[] val, int[] wt) {
        int[] dp = new int[W + 1];
        for (int i = 0; i < wt.length; i++)
            for (int j = W; j >= wt[i]; j--)
                dp[j] = Math.max(dp[j], val[i] + dp[j - wt[i]]);
        return dp[W];
    }
}

Code (Python)

class Solution:
    def knapsack(self, W, val, wt):
        dp = [0] * (W + 1)
        for i in range(len(wt)):
            for j in range(W, wt[i] - 1, -1):
                dp[j] = max(dp[j], val[i] + dp[j - wt[i]])
        return dp[W]

Contribution and Support

For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: Any Questions. Let’s make this learning journey more collaborative!

⭐ If you find this helpful, please give this repository a star! ⭐

---

📍Visitor Count