Definition
- 0/1 Knapsack – a bounded selection problem where each item is either fully included or excluded.
- State –
dp[c]is the maximum value achievable with remaining capacityc. - Recurrence – for each item,
dp[c] = max(dp[c], dp[c - weight] + value)for c from capacity down to weight. - Downward sweep – ensures
dp[c - weight]has not yet been updated for the current item, so each item counts at most once. - 2D form –
dp[i][c] = max(dp[i-1][c], dp[i-1][c - weight[i]] + value[i])when the item fits. - Complexity – O(N * C) time, O(C) space with the single-row trick.
A treasury officer at National Bank of India must load a secure cash van that holds a limited total weight, choosing among sealed cassettes each with a weight and a value. Each cassette can be loaded at most once. For every capacity she asks: does adding this cassette beat leaving it out?
Understanding the Concepts
What is the 0/1 Knapsack problem?
The 0/1 Knapsack problem gives you a set of items, each with a weight and a value, and a knapsack with a maximum weight capacity. You must choose a subset of items that maximises total value without exceeding the capacity. Each item is either taken completely or not taken at all: there is no fractional selection.
This is the foundational problem of the 0/1 Knapsack dynamic programming pattern, and many interview problems reduce to it: subset sum, partition equal subset, target sum, and count of subsets.
package com.bank.dsa;
public class Knapsack01Basic {
public static int knapsack(int[] weights, int[] values, int capacity) {
int n = weights.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 (weights[i - 1] <= c) {
dp[i][c] = Math.max(dp[i][c],
dp[i - 1][c - weights[i - 1]] + values[i - 1]); // include item i
}
}
}
return dp[n][capacity];
}
public static void main(String[] args) {
int[] weights = {1, 3, 4, 5};
int[] values = {1, 4, 5, 7};
int capacity = 7;
System.out.println("Max value: " + knapsack(weights, values, capacity));
}
}
Max value: 9
Why does the problem exist?
Resource allocation under constraints is one of the most common problems in computing and business. A bank has a fixed capital budget and must choose which loan deals to fund. An investment advisor must select products within a client's budget. A cloud engineer must pack services onto servers without exceeding memory. All of these are knapsack problems in disguise.
How does the 2D recurrence work?
The 2D table dp[i][c] stores the maximum value using the first i items with a capacity of c. At each item, we have two choices:
- Exclude: skip item i, so dp[i][c] = dp[i-1][c].
- Include: take item i (if it fits), so dp[i][c] = dp[i-1][c - weight[i]] + value[i].
We take the maximum of the two. The first row dp[0][c] is all zeros because with zero items the value is zero. The answer is dp[n][capacity].
How does the 1D space optimisation work?
Since each row dp[i] depends only on dp[i-1], we can collapse the table to a single array. The critical detail is the sweep direction: we iterate capacity from high to low so that when we read dp[c - weight], it still holds the value from the previous item's pass.
package com.bank.dsa;
public class Knapsack01Optimised {
public static int knapsack(int[] weights, int[] values, int capacity) {
int[] dp = new int[capacity + 1];
for (int i = 0; i < weights.length; i++) {
for (int c = capacity; c >= weights[i]; c--) { // downward sweep
dp[c] = Math.max(dp[c], values[i] + dp[c - weights[i]]);
}
}
return dp[capacity];
}
public static void main(String[] args) {
int[] weights = {1, 3, 4, 5};
int[] values = {1, 4, 5, 7};
int capacity = 7;
System.out.println("Max value: " + knapsack(weights, values, capacity));
}
}
Max value: 9
Why must the capacity loop run downward?
The downward sweep is the key correctness detail. When we update dp[c], we read dp[c - weight], which needs to hold the value from the previous item (row i-1). If we swept upward (from low to high), dp[c - weight] might already have been updated with the current item, which would allow the same item to be used multiple times. That would silently solve the unbounded knapsack instead.
package com.bank.dsa;
public class SweepDirectionDemo {
// WRONG: upward sweep allows item reuse (unbounded knapsack)
public static int knapsackUpward(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++) // upward: item reused!
dp[c] = Math.max(dp[c], v[i] + dp[c - w[i]]);
return dp[cap];
}
// CORRECT: downward sweep enforces use-once
public static int knapsackDownward(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--) // downward: item used once
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, 4};
int cap = 7;
System.out.println("Upward (unbounded): " + knapsackUpward(w, v, cap)); // 10
System.out.println("Downward (0/1): " + knapsackDownward(w, v, cap)); // 7
}
}
Upward (unbounded): 10
Downward (0/1): 7
How do you reconstruct which items were chosen?
With the 2D table, backtrack from dp[n][capacity]. If dp[i][c] differs from dp[i-1][c], item i was included. Reduce c by weight[i] and move to row i-1. Otherwise item i was excluded and you move to row i-1 at the same c.
package com.bank.dsa;
import java.util.ArrayList;
import java.util.List;
public class KnapsackReconstruct {
public static List<Integer> chosenItems(int[] weights, int[] values, int capacity) {
int n = weights.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];
if (weights[i - 1] <= c)
dp[i][c] = Math.max(dp[i][c], dp[i - 1][c - weights[i - 1]] + values[i - 1]);
}
List<Integer> items = new ArrayList<>();
int c = capacity;
for (int i = n; i > 0; i--) {
if (dp[i][c] != dp[i - 1][c]) {
items.add(i - 1); // item index (0-based)
c -= weights[i - 1];
}
}
return items;
}
public static void main(String[] args) {
int[] w = {1, 3, 4, 5};
int[] v = {1, 4, 5, 7};
System.out.println("Chosen items: " + chosenItems(w, v, 7));
}
}
Chosen items: [2, 1]
How is 0/1 Knapsack different from Unbounded Knapsack?
| Aspect | 0/1 Knapsack | Unbounded Knapsack |
|---|---|---|
| Item usage | Each item used at most once | Each item used unlimited times |
| Capacity sweep | High to low (downward) | Low to high (upward) |
| dp[c - w] reads | Previous item's value | Current item's value (allows reuse) |
| Example | Pick loan deals (each once) | Buy investment units (unlimited) |
| 2D recurrence | dp[i-1][c - w] (previous row) | dp[i][c - w] (same row) |
The only code difference is the direction of the inner loop. This makes the sweep direction the single most important detail in knapsack problems.
What are the edge cases?
When all items weigh more than the capacity, the answer is zero because nothing fits. When the capacity is zero, the answer is also zero. When there is only one item, the answer is its value if it fits, or zero otherwise.
package com.bank.dsa;
public class KnapsackEdgeCases {
public static void main(String[] args) {
System.out.println(Knapsack01Optimised.knapsack(new int[]{10, 20}, new int[]{5, 10}, 5)); // 0
System.out.println(Knapsack01Optimised.knapsack(new int[]{3}, new int[]{7}, 5)); // 7
System.out.println(Knapsack01Optimised.knapsack(new int[]{}, new int[]{}, 10)); // 0
}
}
0
7
0
When should you use 0/1 Knapsack in banking?
The National Bank of India uses this pattern whenever a fixed budget must be allocated across one-time opportunities. Rajesh in the treasury selects which sealed cash cassettes to load in the secure van to maximise the transported value within the van's weight limit. The capital allocation team selects which loan deals to fund within a quarterly budget. The IT team selects which infrastructure upgrades to approve within an annual budget.
package com.bank.service;
import java.math.BigDecimal;
public class LoanDealSelector {
public static BigDecimal maxProfit(int[] capitalNeeded, BigDecimal[] expectedProfit, int budget) {
int n = capitalNeeded.length;
BigDecimal[] dp = new BigDecimal[budget + 1];
for (int c = 0; c <= budget; c++) dp[c] = BigDecimal.ZERO;
for (int i = 0; i < n; i++) {
for (int c = budget; c >= capitalNeeded[i]; c--) {
BigDecimal include = expectedProfit[i].add(dp[c - capitalNeeded[i]]);
if (include.compareTo(dp[c]) > 0) dp[c] = include;
}
}
return dp[budget];
}
public static void main(String[] args) {
int[] capital = {10, 30, 40, 50};
BigDecimal[] profit = {
new BigDecimal("1.5"), new BigDecimal("4.2"),
new BigDecimal("5.8"), new BigDecimal("7.1")
};
System.out.println("Max profit: " + maxProfit(capital, profit, 70) + " crore");
}
}
Max profit: 10.0 crore
What should a senior engineer know?
The knapsack problem is NP-hard in general, and the O(N * C) solution is pseudo-polynomial: it is polynomial in the numeric value of C, not in the number of bits needed to represent C. This means if C is astronomically large (say, 10^18), the DP is infeasible and you need approximation algorithms or branch-and-bound.
The meet-in-the-middle technique splits items into two halves, enumerates all subsets of each half in O(2^(N/2)), and combines them with sorting and binary search. This is practical when N is around 40 and C is too large for the standard DP.
In production systems, the knapsack formulation also models resource scheduling, container packing, and feature selection under a compute budget.
Visual Overview
0/1 Knapsack: 1D Array with Downward Sweep
────────────────────────────────────────────
Items: weight=[1,3,4,5], value=[1,4,5,7], capacity=7
dp[] initially: [0, 0, 0, 0, 0, 0, 0, 0]
0 1 2 3 4 5 6 7 ← capacity
Item 0 (w=1, v=1): sweep 7→1
dp[] = [0, 1, 1, 1, 1, 1, 1, 1]
Item 1 (w=3, v=4): sweep 7→3
dp[] = [0, 1, 1, 4, 5, 5, 5, 5]
Item 2 (w=4, v=5): sweep 7→4
dp[] = [0, 1, 1, 4, 5, 6, 6, 9]
Item 3 (w=5, v=7): sweep 7→5
dp[] = [0, 1, 1, 4, 5, 7, 8, 9]
Answer: dp[7] = 9 (items with w=3,v=4 and w=4,v=5)
Sweep Direction Comparison ────────────────────────── Downward (0/1): Upward (Unbounded): c = 7 → 6 → ... → 1 c = 1 → 2 → ... → 7 dp[c-w] = old value dp[c-w] = new value Item used once Item reused freely
Key Takeaway
The 0/1 Knapsack is the foundational bounded-selection dynamic programming problem. For each item you make a binary decision: include it or skip it. The one-dimensional optimisation keeps a single array dp[c] where c ranges from zero to the total capacity, and for each item you sweep capacity from high to low, updating dp[c] with the maximum of its current value and dp[c - weight] + value.
The downward sweep is the entire correctness trick. When you update dp[c] and read dp[c - weight], that value has not yet been touched for the current item, so it still reflects the best value using only the previous items. This enforces the use-each-item-once constraint. If you swept upward, dp[c - weight] might already include the current item, silently turning the problem into unbounded knapsack.
At National Bank of India, Rajesh used this pattern to select which loan deals to fund within a quarterly capital budget, each deal either fully funded or skipped, maximising total expected profit. The one-dimensional array with the downward sweep ran fast even for large deal lists, and the direction of the loop was a deliberate correctness decision.
Remember one sentence: 0/1 Knapsack sweeps capacity downward so each item is counted at most once, and the answer sits at dp[capacity].
---