Definition
- Tabulated 0/1 Knapsack – a bottom-up iterative solution filling a table of best values.
- 2D recurrence –
dp[i][c] = max(dp[i-1][c], value[i] + dp[i-1][c - weight[i]])when the item fits. - Space optimisation – collapse to one row
dp[c]and sweep capacity from high to low. - Downward sweep – ensures
dp[c - weight]holds the previous item's value, enforcing use-once. - Reconstruction – backtrack from
dp[n][C]in the 2D table to find which items were included. - Complexity – O(N * C) time; space from O(N * C) down to O(C) with the single-row trick.
The National Bank of India allocates a fixed capital budget across one-time loan deals, each either fully funded or skipped. The team builds a table of best profit for every budget level as they consider each deal, then collapses it to a single running row for efficiency.
Understanding the Concepts
What is tabulated 0/1 Knapsack?
The tabulated (bottom-up) 0/1 Knapsack fills a 2D table iteratively without recursion. Each cell dp[i][c] stores the maximum value achievable using the first i items within capacity c. The table is filled row by row from the first item to the last, and the answer is in the bottom-right cell.
package com.bank.dsa;
public class KnapsackTabulation {
public static int solve(int[] weight, int[] value, int capacity) {
int n = weight.length;
int[][] dp = new int[n + 1][capacity + 1];
for (int i = 1; i <= n; i++) {
for (int c = 0; c <= capacity; c++) {
dp[i][c] = dp[i - 1][c]; // exclude item i
if (weight[i - 1] <= c) {
dp[i][c] = Math.max(dp[i][c],
value[i - 1] + dp[i - 1][c - weight[i - 1]]); // include
}
}
}
return dp[n][capacity];
}
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
How does the 2D recurrence work?
At each item i and capacity c, there are two choices. Excluding item i means the best value is the same as using only the first i-1 items at capacity c: dp[i-1][c]. Including item i (if it fits) means adding its value to the best using the first i-1 items at the reduced capacity: value[i] + dp[i-1][c - weight[i]]. We take the maximum.
Row 0 is all zeros because with zero items the value is zero. Column 0 is all zeros because with zero capacity nothing fits.
How do you collapse the table to one row?
Since each row depends only on the row directly above, we can keep a single array dp[c] and process items one at a time. For each item, we update the array in place.
package com.bank.dsa;
public class KnapsackOneRowTab {
public static int solve(int[] weight, int[] value, int capacity) {
int[] dp = new int[capacity + 1];
for (int i = 0; i < weight.length; i++) {
for (int c = capacity; c >= weight[i]; c--) { // downward!
dp[c] = Math.max(dp[c], value[i] + dp[c - weight[i]]);
}
}
return dp[capacity];
}
public static void main(String[] args) {
int[] w = {1, 3, 4, 5};
int[] v = {1, 4, 5, 7};
System.out.println("Max value (1D): " + solve(w, v, 7));
}
}
Max value (1D): 9
Why must the capacity loop run downward?
The downward sweep guarantees that when we read dp[c - weight[i]], it still holds the value from the previous item's pass (row i-1). If we swept upward, dp[c - weight[i]] might already have been updated with the current item, allowing reuse.
package com.bank.dsa;
public class SweepDirectionDemo {
public static int downward(int[] w, int[] v, int cap) {
int[] dp = new int[cap + 1];
for (int i = 0; i < w.length; i++)
for (int c = cap; c >= w[i]; c--) // 0/1: each item once
dp[c] = Math.max(dp[c], v[i] + dp[c - w[i]]);
return dp[cap];
}
public static int upward(int[] w, int[] v, int cap) {
int[] dp = new int[cap + 1];
for (int i = 0; i < w.length; i++)
for (int c = w[i]; c <= cap; c++) // unbounded: item reused
dp[c] = Math.max(dp[c], v[i] + dp[c - w[i]]);
return dp[cap];
}
public static void main(String[] args) {
int[] w = {2, 3};
int[] v = {3, 5};
System.out.println("Downward (0/1): " + downward(w, v, 7));
System.out.println("Upward (unbounded): " + upward(w, v, 7));
}
}
Downward (0/1): 8
Upward (unbounded): 11
How do you reconstruct which items were chosen?
With the full 2D table, backtrack from dp[n][C]. If dp[i][c] != dp[i-1][c], item i was included. Move to row i-1 with capacity c - weight[i]. Otherwise move to row i-1 at the same capacity.
package com.bank.dsa;
import java.util.ArrayList;
import java.util.List;
public class KnapsackReconstruct {
public static List<Integer> reconstruct(int[] w, int[] v, int cap) {
int n = w.length;
int[][] dp = new int[n + 1][cap + 1];
for (int i = 1; i <= n; i++)
for (int c = 0; c <= cap; c++) {
dp[i][c] = dp[i - 1][c];
if (w[i - 1] <= c)
dp[i][c] = Math.max(dp[i][c], v[i - 1] + dp[i - 1][c - w[i - 1]]);
}
List<Integer> chosen = new ArrayList<>();
int c = cap;
for (int i = n; i > 0; i--)
if (dp[i][c] != dp[i - 1][c]) {
chosen.add(i - 1);
c -= w[i - 1];
}
return chosen;
}
public static void main(String[] args) {
System.out.println(reconstruct(new int[]{1, 3, 4, 5}, new int[]{1, 4, 5, 7}, 7));
}
}
[2, 1]
How is tabulation different from memoization?
| Aspect | Tabulation (bottom-up) | Memoization (top-down) |
|---|---|---|
| Iteration | Nested loops, no recursion | Recursive with cache |
| Subproblems | Fills entire table | Solves only reachable states |
| Stack overflow | No risk | Risk for large inputs |
| Space optimisation | Easy (collapse to 1D) | Difficult (stack holds state) |
| Code style | Less natural but efficient | Natural decision tree |
What are common mistakes?
The most common mistake in the 1D version is sweeping capacity upward, which silently solves unbounded knapsack. The second most common mistake is using the wrong array indices when translating between 1-based item indexing and 0-based array access.
// WRONG: upward sweep allows reuse
for (int c = weight[i]; c <= capacity; c++)
dp[c] = Math.max(dp[c], value[i] + dp[c - weight[i]]);
// CORRECT: downward sweep, each item once
for (int c = capacity; c >= weight[i]; c--)
dp[c] = Math.max(dp[c], value[i] + dp[c - weight[i]]);
What are the edge cases?
When all weights exceed the capacity, the answer is zero. When capacity is zero, nothing fits. When every item fits, the answer is the sum of all values.
package com.bank.dsa;
public class KnapsackTabEdge {
public static void main(String[] args) {
System.out.println(KnapsackOneRowTab.solve(new int[]{10}, new int[]{5}, 3)); // 0
System.out.println(KnapsackOneRowTab.solve(new int[]{1, 2}, new int[]{3, 4}, 10)); // 7
}
}
0
7
When should you use tabulated knapsack in banking?
At the National Bank of India, the treasury allocates a fixed capital budget across one-time loan deals using the 1D tabulated knapsack. Each deal is either fully funded or skipped. The single-row approach keeps memory usage low even for large deal lists.
package com.bank.service;
import java.math.BigDecimal;
public class DealAllocator {
public static BigDecimal maxReturn(int[] capital, BigDecimal[] returnRate, int budget) {
BigDecimal[] dp = new BigDecimal[budget + 1];
for (int i = 0; i <= budget; i++) dp[i] = BigDecimal.ZERO;
for (int i = 0; i < capital.length; i++) {
for (int c = budget; c >= capital[i]; c--) {
BigDecimal inc = returnRate[i].add(dp[c - capital[i]]);
if (inc.compareTo(dp[c]) > 0) dp[c] = inc;
}
}
return dp[budget];
}
public static void main(String[] args) {
int[] cap = {10, 20, 30};
BigDecimal[] ret = {new BigDecimal("2.5"), new BigDecimal("5.0"), new BigDecimal("6.0")};
System.out.println("Max return: " + maxReturn(cap, ret, 40) + " crore");
}
}
Max return: 7.5 crore
What should a senior engineer know?
A senior engineer should understand that the tabulated version is preferred in production because it avoids recursion stack overflow and makes space optimisation straightforward. The 1D trick reduces memory from O(N * C) to O(C), which matters when C is large.
The direction of the capacity loop is the single most important correctness detail. A senior candidate should be able to explain, without hesitation, that downward preserves the previous item's values (use-once) and upward allows reuse (unbounded).
For item reconstruction, the full 2D table or a parallel decision array is needed, which means the 1D optimisation trades reconstruction ability for space savings.
Visual Overview
0/1 Knapsack: 2D Table to 1D Row
──────────────────────────────────
2D Table (items x capacity):
c=0 c=1 c=2 c=3 c=4 c=5 c=6 c=7
i=0: 0 0 0 0 0 0 0 0
i=1: 0 1 1 1 1 1 1 1
i=2: 0 1 1 4 5 5 5 5
i=3: 0 1 1 4 5 6 6 9 ← answer
i=4: 0 1 1 4 5 7 8 9
Row i depends ONLY on row i-1
→ Collapse to single row, sweep c downward
1D Row after each item:
[0,0,0,0,0,0,0,0] → [0,1,1,1,1,1,1,1]
→ [0,1,1,4,5,5,5,5] → [0,1,1,4,5,6,6,9]
→ [0,1,1,4,5,7,8,9]
Key Takeaway
The tabulated 0/1 Knapsack turns the recursive include-or-exclude logic into a bottom-up table filled iteratively. Each cell dp[i][c] takes the maximum of excluding the item (copy the row above) or including it when it fits (add its value to the row above at reduced capacity). The answer is in the bottom-right cell.
The space optimisation collapses the table to a single row by sweeping capacity from high to low for each item. The downward sweep guarantees that dp[c - weight] holds the previous item's value, enforcing use-once. Sweeping upward would read an already-updated value and silently turn the problem into unbounded knapsack.
At the National Bank of India, the treasury used the 1D tabulated knapsack to allocate a fixed capital budget across one-time loan deals, maximising total expected return. The single-row approach kept memory low even for large deal counts, and the downward sweep was a deliberate correctness decision.
The senior-level insight is that the sweep direction is the single toggle between use-once and use-unlimited, and that item reconstruction requires the full 2D table or a separate decision array.
Remember one sentence: fill the table bottom-up and collapse to one row with a downward capacity sweep so each item counts exactly once.
---