Given n items, each with a specific weight and value, and a knapsack with a capacity of W, the task is to put the items in the knapsack such that the sum of weights of the items <= W and the sum of values associated with them is maximized.
Here’s the [Problem Link] to begin with.
Note: You can either place an item entirely in the bag or leave it out entirely. Also, each item is available in single quantity.
Examples :
Input: W = 4,val[]= [1, 2, 3],wt[]= [4, 5, 1]
Output: 3
Explanation: Choose the last item, which weighs 1 unit and has a value of 3.
Input: W = 3,val[]= [1, 2, 3],wt[]= [4, 5, 6]
Output: 0
Explanation: Every item has a weight exceeding the knapsack's capacity (3).
Input: W = 5,val[]= [10, 40, 30, 50],wt[]= [5, 4, 2, 3]
Output: 80
Explanation: Choose the third item (value 30, weight 2) and the last item (value 50, weight 3) for a total value of 80.
Constraints:
2 ≤ val.size() = wt.size() ≤ 103
1 ≤ W ≤ 103
1 ≤ val[i] ≤ 103
1 ≤ wt[i] ≤ 103
Contents:
[show]
Solution 1: Recursion (Brute Force)
Intuition and Approach
At each item index:
- If the item fits (wt[index] ≤ W), consider:
- pick = val[index] + best for remaining capacity (W − wt[index]) with previous items
- not_pick = best without taking this item
- Take max(pick, not_pick).
- Base case: at index 0, if it fits, return its value; else 0.
This explores all subsets and forms the basis for memoization.
Code Implementation
class Solution:
def solve(self, index, W, val, wt):
# Base: only first item available
if index == 0:
if wt[index] <= W:
return val[index]
return 0
# If current item doesn't fit, can't pick it
if wt[index] > W:
pick = float("-inf")
else:
# Option to pick current item
pick = val[index] + self.solve(index - 1, W - wt[index], val, wt)
# Option to not pick current item
not_pick = 0 + self.solve(index - 1, W, val, wt)
# Max of both choices
return max(pick, not_pick)
def knapsack(self, W, val, wt):
n = len(wt)
return self.solve(n - 1, W, val, wt)Code Explanation
- Recursively tries both decisions where feasible and returns the maximum achievable value.
- The base case anchors the recursion at the first item.
Time and Space Complexity
- Precise: Time O(2^n), Space O(n) recursion depth.
- Simplified: Exponential time; linear stack space.
Conclusion
Great for understanding the choice structure, but too slow for larger n or W.
Solution 2: Memoization (Top-Down DP)
Intuition and Approach
The same (index, W) states repeat frequently. Cache results in a 2D dp table to avoid recomputation:
- dp[index][W] stores the best value achievable considering items up to index with capacity W.
- Before computing, return cached value if available.
Code Implementation
class Solution:
def solve(self, index, W, val, wt, dp):
# Base: first item
if index == 0:
if wt[index] <= W:
return val[index]
return 0
# Cached result
if dp[index][W] != -1:
return dp[index][W]
# Decision: pick if it fits, else -inf
if wt[index] > W:
pick = float("-inf")
else:
pick = val[index] + self.solve(index - 1, W - wt[index], val, wt, dp)
not_pick = 0 + self.solve(index - 1, W, val, wt, dp)
dp[index][W] = max(pick, not_pick)
return dp[index][W]
def knapsack(self, W, val, wt):
n = len(wt)
dp = [[-1 for _ in range(0, W + 1)] for _ in range(n)]
return self.solve(n - 1, W, val, wt, dp)Code Explanation
- Stores results for each state to ensure each is solved once.
- Converts exponential recursion into polynomial time.
Time and Space Complexity
- Precise: Time O(n × W), Space O(n × W) for dp + O(n) stack.
- Simplified: Polynomial time and space; suitable for typical constraints.
Conclusion
Ideal upgrade over pure recursion, retaining clarity while being efficient.
Solution 3: Tabulation (Bottom-Up DP)
Intuition and Approach
Iteratively build dp where dp[i][w] is the max value using items up to index i with capacity w.
- Initialize first row: for all capacities w ≥ wt, dp[w] = val.
- Transition:
- If wt[i] ≤ w: pick = val[i] + dp[i−1][w − wt[i]]
- not_pick = dp[i−1][w]
- dp[i][w] = max(pick, not_pick)
Code Implementation
class Solution:
def knapsack(self, W, val, wt):
n = len(wt)
# dp[i][w] -> max value using items up to i with capacity w
dp = [[0 for _ in range(0, W + 1)] for _ in range(n)]
# Initialize first item row
for w in range(0, W + 1):
if wt <= w:
dp[w] = val
# Fill table
for index in range(1, n):
for W_ in range(0, W + 1):
if wt[index] > W_:
pick = float("-inf")
else:
pick = val[index] + dp[index - 1][W_ - wt[index]]
not_pick = 0 + dp[index - 1][W_]
dp[index][W_] = max(pick, not_pick)
return dp[n - 1][W]Code Explanation
- Bottom-up computation ensures all subproblems are solved once in increasing order of i and capacity.
- Final answer resides at dp[n−1][W].
Time and Space Complexity
- Precise: Time O(n × W), Space O(n × W).
- Simplified: Polynomial time and space; easy to trace and debug.
Conclusion
A robust, iterative DP that’s straightforward to implement and reason about.
Solution 4: Space Optimization using 2 One-Dimensional Arrays
Intuition and Approach
Each row depends only on the previous row, so keep just two 1D arrays:
- prev for dp[i−1][·] and curr for dp[i][·].
- After finishing a row, assign prev = curr.
Code Implementation
class Solution:
def knapsack(self, W, val, wt):
n = len(wt)
prev = [0 for _ in range(0, W + 1)]
# Initialize first item row
for w in range(0, W + 1):
if wt <= w:
prev[w] = val
# Build next rows
for index in range(1, n):
curr = [0 for _ in range(0, W + 1)]
for W_ in range(0, W + 1):
if wt[index] > W_:
pick = float("-inf")
else:
pick = val[index] + prev[W_ - wt[index]]
not_pick = 0 + prev[W_]
curr[W_] = max(pick, not_pick)
prev = curr
return prev[W]Code Explanation
- Reduces space from O(n × W) to O(W) while preserving all transitions.
- Maintains correctness by using the previous row only.
Time and Space Complexity
- Precise: Time O(n × W), Space O(W).
- Simplified: Same time, linear space in capacity.
Conclusion
A practical and memory-efficient improvement that’s often required in interviews.
Solution 5: Space Optimization using a Single 1D Array
Intuition and Approach
Update the same array in reverse capacity order to avoid overwriting needed values:
- Iterate W_ from W down to 0 for each item to ensure dp[w − wt[i]] still refers to the previous iteration’s state.
Code Implementation
class Solution:
def knapsack(self, W, val, wt):
n = len(wt)
prev = [0 for _ in range(0, W + 1)]
# Initialize first item
for w in range(0, W + 1):
if wt <= w:
prev[w] = val
# Single-array optimization: iterate capacity backward
for index in range(1, n):
for W_ in range(W, -1, -1):
if wt[index] > W_:
pick = float("-inf")
else:
pick = val[index] + prev[W_ - wt[index]]
not_pick = 0 + prev[W_]
prev[W_] = max(pick, not_pick)
return prev[W]Code Explanation
- Backward iteration ensures correctness by preventing intra-row contamination.
- Achieves the optimal O(W) space with clean logic.
Time and Space Complexity
- Precise: Time O(n × W), Space O(W).
- Simplified: Best practical DP for classic 0-1 Knapsack.
Final Notes and Tips
- Base initialization for the first item row is crucial to seed the DP correctly.
- Using float(“-inf”) for “cannot pick” keeps max logic clean; alternatively, conditionally skip computing pick.
- The single-array backward iteration is the optimal space pattern for 0-1 knapsack; forward iteration would incorrectly reuse updated states.
- For very large W, consider value-based DP or alternative heuristics, but for typical constraints, these DP formulations are standard.
Mastering these five formulations, especially the transition from recursion to O(W) space, builds strong dynamic programming intuition and prepares for a wide range of knapsack-like problems.
For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.
