Definition
- 0/1 Knapsack (memoized) – a top-down recursive solution that caches subproblem results for each (item, capacity) pair.
- Binary choice – at each item, include it (reducing capacity) or exclude it (same capacity).
- State –
(index, remainingCapacity)uniquely identifies a subproblem. - Cache – a 2D array
memo[index][capacity]stores computed results, avoiding redundant work. - Complexity – O(N * C) time and O(N * C) space, pseudo-polynomial.
- Conversion – directly translates to bottom-up tabulation for 1D space optimisation.
The National Bank of India has a fixed quarterly capital budget and a shortlist of loan applications. Each loan needs a certain amount of capital and promises a certain profit. For each loan, the committee asks: if we fund this one, does the remaining budget yield more total profit than if we skip it? The memoized recursion tries both paths and caches the answer for each loan-and-budget combination.
Understanding the Concepts
What is the memoized 0/1 Knapsack?
The memoized (top-down) 0/1 Knapsack starts from the full set of items and full capacity, and at each item makes a binary choice: include it or skip it. The recursion explores both branches and returns the maximum value. Because many branches lead to the same (item, capacity) state, we cache results to avoid redundant computation.
package com.bank.dsa;
import java.util.Arrays;
public class KnapsackMemoized {
private static int[][] memo;
private static int[] weight;
private static int[] value;
public static int solve(int[] w, int[] v, int capacity) {
weight = w;
value = v;
int n = w.length;
memo = new int[n][capacity + 1];
for (int[] row : memo) Arrays.fill(row, -1);
return dp(0, capacity);
}
private static int dp(int i, int cap) {
if (i == weight.length) return 0; // no items left
if (memo[i][cap] != -1) return memo[i][cap];
int exclude = dp(i + 1, cap); // skip item i
int include = 0;
if (weight[i] <= cap) {
include = value[i] + dp(i + 1, cap - weight[i]); // take item i
}
return memo[i][cap] = Math.max(exclude, include);
}
public static void main(String[] args) {
int[] w = {1, 3, 4, 5};
int[] v = {1, 4, 5, 7};
System.out.println("Max value: " + solve(w, v, 7));
}
}
Max value: 9
Why use memoization instead of tabulation?
Memoization preserves the natural recursion structure, making the code easier to write and understand. It also has the advantage of solving only reachable states. If the capacity is large but most (item, capacity) combinations are never visited, memoization skips them entirely, while tabulation would fill the entire table.
On the other hand, tabulation avoids recursion stack overhead and makes the 1D space optimisation straightforward. In practice, both approaches give the same asymptotic complexity.
How does the recursion tree work?
At each item, the tree branches into two: exclude (same capacity, next item) and include (reduced capacity, next item). Without memoization, this tree has 2^N leaves because each item doubles the branches. With memoization, each unique (item, capacity) pair is computed once, so the total work is at most N * C.
package com.bank.dsa;
public class KnapsackRecursionTrace {
private static int computations = 0;
private static int cacheHits = 0;
private static int[][] memo;
public static int dp(int[] w, int[] v, int i, int cap) {
if (i == w.length) return 0;
if (memo[i][cap] != -1) { cacheHits++; return memo[i][cap]; }
computations++;
int exc = dp(w, v, i + 1, cap);
int inc = w[i] <= cap ? v[i] + dp(w, v, i + 1, cap - w[i]) : 0;
return memo[i][cap] = Math.max(exc, inc);
}
public static void main(String[] args) {
int[] w = {1, 3, 4, 5};
int[] v = {1, 4, 5, 7};
memo = new int[w.length][8];
for (int[] row : memo) java.util.Arrays.fill(row, -1);
computations = 0; cacheHits = 0;
System.out.println("Max value: " + dp(w, v, 0, 7));
System.out.println("Computations: " + computations);
System.out.println("Cache hits: " + cacheHits);
}
}
Max value: 9
Computations: 15
Cache hits: 1
How do you convert memoization to tabulation?
The memoized recursion directly translates to a bottom-up table. Replace the recursion with nested loops iterating items from last to first and capacities from 0 to C.
package com.bank.dsa;
public class KnapsackMemoToTab {
// Memoized (top-down)
public static int solveMemo(int[] w, int[] v, int cap) {
int n = w.length;
int[][] memo = new int[n + 1][cap + 1];
for (int[] row : memo) java.util.Arrays.fill(row, -1);
return dpMemo(w, v, 0, cap, memo);
}
private static int dpMemo(int[] w, int[] v, int i, int cap, int[][] memo) {
if (i == w.length) return 0;
if (memo[i][cap] != -1) return memo[i][cap];
int exc = dpMemo(w, v, i + 1, cap, memo);
int inc = w[i] <= cap ? v[i] + dpMemo(w, v, i + 1, cap - w[i], memo) : 0;
return memo[i][cap] = Math.max(exc, inc);
}
// Tabulated (bottom-up)
public static int solveTab(int[] w, int[] v, int cap) {
int n = w.length;
int[][] dp = new int[n + 1][cap + 1];
for (int i = n - 1; i >= 0; i--) {
for (int c = 0; c <= cap; c++) {
dp[i][c] = dp[i + 1][c]; // exclude
if (w[i] <= c)
dp[i][c] = Math.max(dp[i][c], v[i] + dp[i + 1][c - w[i]]);
}
}
return dp[0][cap];
}
public static void main(String[] args) {
int[] w = {1, 3, 4, 5};
int[] v = {1, 4, 5, 7};
System.out.println("Memo: " + solveMemo(w, v, 7));
System.out.println("Tab: " + solveTab(w, v, 7));
}
}
Memo: 9
Tab: 9
How is memoized 0/1 Knapsack different from tabulated?
| Aspect | Memoized (top-down) | Tabulated (bottom-up) |
|---|---|---|
| Direction | Starts at item 0 and full capacity | Starts at last item and fills backward |
| Subproblems | Solves only reachable states | Fills entire table |
| Space optimisation | Hard (recursion stack holds state) | Easy (collapse to 1D array) |
| Stack overflow | Risk for large N or C | None |
| Code clarity | Natural decision tree | Nested loops |
What are common mistakes?
The most common mistake is forgetting to initialise the memo array to -1 (or another sentinel). If the memo starts at 0, a subproblem with a genuine answer of 0 (no items fit) appears already solved, and the recursion returns early with a wrong answer.
// WRONG: memo initialised to 0, genuine 0 looks like "already computed"
int[][] memo = new int[n][cap + 1]; // all zeros by default
// CORRECT: initialise to -1 as sentinel
int[][] memo = new int[n][cap + 1];
for (int[] row : memo) Arrays.fill(row, -1);
Another mistake is using the wrong direction for the item index. If recursion goes from 0 to n, the base case is i == n. If it goes from n-1 to 0, the base case is i < 0.
What are the edge cases?
When capacity is zero, the answer is zero (nothing fits). When no items fit, the answer is zero. When all items fit, the answer is the total of all values.
package com.bank.dsa;
public class KnapsackMemoEdge {
public static void main(String[] args) {
System.out.println(KnapsackMemoized.solve(new int[]{5}, new int[]{10}, 0)); // 0
System.out.println(KnapsackMemoized.solve(new int[]{10}, new int[]{5}, 3)); // 0
System.out.println(KnapsackMemoized.solve(new int[]{1,2}, new int[]{3,4}, 5)); // 7
}
}
0
0
7
When should you use memoized knapsack in banking?
At the National Bank of India, the capital allocation committee evaluates loan applications. Each application needs a certain capital commitment and promises a certain profit. The committee runs the memoized recursion to explore the include-or-exclude decision tree and find the subset that maximises total profit within the quarterly budget.
package com.bank.service;
import java.math.BigDecimal;
import java.util.Arrays;
public class LoanAllocationMemo {
private static BigDecimal[][] memo;
private static int[] capital;
private static BigDecimal[] profit;
public static BigDecimal maxProfit(int[] cap, BigDecimal[] prof, int budget) {
capital = cap;
profit = prof;
memo = new BigDecimal[cap.length][budget + 1];
return dp(0, budget);
}
private static BigDecimal dp(int i, int budget) {
if (i == capital.length) return BigDecimal.ZERO;
if (memo[i][budget] != null) return memo[i][budget];
BigDecimal exc = dp(i + 1, budget);
BigDecimal inc = BigDecimal.ZERO;
if (capital[i] <= budget)
inc = profit[i].add(dp(i + 1, budget - capital[i]));
return memo[i][budget] = exc.max(inc);
}
public static void main(String[] args) {
int[] cap = {10, 30, 40, 50};
BigDecimal[] prof = {bd("1.5"), bd("4.2"), bd("5.8"), bd("7.1")};
System.out.println("Max profit: " + maxProfit(cap, prof, 70) + " crore");
}
private static BigDecimal bd(String s) { return new BigDecimal(s); }
}
Max profit: 10.0 crore
What should a senior engineer know?
A senior engineer should understand that the memoized version and the tabulated version solve exactly the same set of subproblems with the same complexity. The choice between them is practical: memoization is more natural for tree-shaped decision problems and skips unreachable states, while tabulation avoids stack limits and enables straightforward space optimisation.
The complexity O(N * C) is pseudo-polynomial. A memo array of size 10,000 * 1,000,000 would require 10 billion entries, so very large capacities need different approaches like meet-in-the-middle.
In Java, int[][] arrays initialised with -1 are more cache-friendly than HashMap, so prefer array-based memoization when the state space is dense.
Visual Overview
Memoized 0/1 Knapsack: Recursion Tree
──────────────────────────────────────
dp(0, 7)
├─ EXCLUDE item 0 → dp(1, 7)
│ ├─ EXCLUDE item 1 → dp(2, 7)
│ │ ├─ EXCLUDE → dp(3, 7)
│ │ └─ INCLUDE → dp(3, 3)
│ └─ INCLUDE item 1 → dp(2, 4)
│ ├─ EXCLUDE → dp(3, 4)
│ └─ INCLUDE → dp(3, 0)
└─ INCLUDE item 0 → dp(1, 6)
├─ EXCLUDE → dp(2, 6)
└─ INCLUDE → dp(2, 3)
Without memo: 2^4 = 16 leaf calls
With memo: at most 4 * 8 = 32 unique states
Each (item, capacity) pair computed once and cached
Key Takeaway
The memoized 0/1 Knapsack preserves the natural recursive decision tree: at each item, choose the better of including it (if it fits) or excluding it, and recurse on the remaining items. The subproblem is uniquely identified by the item index and the remaining capacity, so a 2D cache ensures each state is solved once.
The advantage of memoization over tabulation is that it solves only reachable states and keeps the code close to the problem's decision structure. The disadvantage is that it uses recursion stack space and makes the 1D space optimisation harder. Both approaches have the same O(N * C) asymptotic complexity.
At the National Bank of India, the capital allocation committee ran the memoized recursion to evaluate which loan applications to fund within a quarterly budget. The recursive structure made the include-or-exclude logic clear for audit purposes, and the cache kept the computation fast.
The senior-level point is that the complexity is pseudo-polynomial: it depends on the numeric value of the capacity, not its bit length. For enormous capacities, meet-in-the-middle or approximation algorithms are needed. Array-based memoization is more cache-friendly than HashMap-based in Java.
Remember one sentence: at each item choose include or exclude, cache by (index, capacity), and the memoized answer equals the tabulated answer with O(N * C) work.
---