Definition
- 0/1 Knapsack – select a subset of items, each used at most once, to maximise total value within a weight capacity.
- Binary choice – every item is either fully included or fully excluded; no fractional selection.
- 2D recurrence –
dp[i][c] = max(dp[i-1][c], profit[i] + dp[i-1][c - weight[i]])when the item fits. - 1D optimisation – a single array swept from high to low capacity enforces the use-once rule.
- Pseudo-polynomial – the complexity O(N * C) depends on the numeric capacity, not its bit length.
- Pattern family – covers subset sum, equal partition, target sum, and bounded counting problems.
The National Bank of India gives Rajesh a fixed investment budget. Each investment product has a cost and an expected return, and he can either buy it once or not at all. He wants the highest total return without exceeding the budget. The 0/1 Knapsack DP decides, for every budget level, the best return achievable by asking item by item whether including it beats leaving it out.
Understanding the Concepts
What is the 0/1 Knapsack pattern?
The 0/1 Knapsack pattern applies whenever you face a set of items, each with a cost and a benefit, and a total budget constraint. Each item is either selected or not: there is no partial selection. You want to maximise (or minimise) the total benefit within the budget.
This pattern is one of the most important in dynamic programming interviews. Many problems reduce to it: subset sum (can you reach a target weight?), partition equal subset (can you split items into two equal-sum groups?), target sum (count subsets that sum to a target), and bounded counting problems.
package com.bank.dsa;
public class KnapsackPattern {
public static int maxProfit(int[] weight, int[] profit, 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
if (weight[i - 1] <= c) {
dp[i][c] = Math.max(dp[i][c],
profit[i - 1] + dp[i - 1][c - weight[i - 1]]); // include
}
}
}
return dp[n][capacity];
}
public static void main(String[] args) {
int[] w = {1, 2, 3, 5};
int[] p = {1, 6, 10, 16};
System.out.println("Max profit: " + maxProfit(w, p, 7));
}
}
Max profit: 22
Why does the 0/1 Knapsack pattern exist?
Resource allocation under constraints is everywhere in business and computing. A bank decides which loan applications to fund within a quarterly capital budget. A project manager selects features to build within a sprint's capacity. A container packer decides which packages to load within a weight limit. All of these are include-or-exclude decisions under a shared constraint, which is the 0/1 Knapsack pattern.
How does the 2D table work internally?
The table has (N + 1) rows and (C + 1) columns. Row zero represents zero items (all values zero). Column zero represents zero capacity (all values zero). Cell dp[i][c] stores the maximum profit using the first i items with capacity c.
For each item i at each capacity c, there are two choices: - **Exclude item i**: dp[i][c] = dp[i-1][c], the best value without this item. - **Include item i** (if weight[i] <= c): dp[i][c] = profit[i] + dp[i-1][c - weight[i]], the item's profit plus the best value with the remaining capacity from the previous items.
We take the maximum of the two. The answer is dp[N][C].
package com.bank.dsa;
public class KnapsackTablePrint {
public static void printTable(int[] w, int[] p, 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], p[i - 1] + dp[i - 1][c - w[i - 1]]);
}
System.out.print(" ");
for (int c = 0; c <= cap; c++) System.out.printf("%4d", c);
System.out.println();
for (int i = 0; i <= n; i++) {
System.out.printf("i=%d: ", i);
for (int c = 0; c <= cap; c++) System.out.printf("%4d", dp[i][c]);
System.out.println();
}
}
public static void main(String[] args) {
printTable(new int[]{1, 3, 4, 5}, new int[]{1, 4, 5, 7}, 7);
}
}
0 1 2 3 4 5 6 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
i=4: 0 1 1 4 5 7 8 9
How do you optimise space to one row?
Since row i depends only on row i-1, we collapse the table to a single array. For each item, we sweep capacity from high to low, updating dp[c] with the maximum of its current value and profit[i] + dp[c - weight[i]]. The downward sweep ensures dp[c - weight[i]] has not been updated yet for the current item.
package com.bank.dsa;
public class KnapsackOneRow {
public static int maxProfit(int[] weight, int[] profit, int capacity) {
int[] dp = new int[capacity + 1];
for (int i = 0; i < weight.length; i++) {
for (int c = capacity; c >= weight[i]; c--) {
dp[c] = Math.max(dp[c], profit[i] + dp[c - weight[i]]);
}
}
return dp[capacity];
}
public static void main(String[] args) {
System.out.println(maxProfit(new int[]{1, 3, 4, 5}, new int[]{1, 4, 5, 7}, 7));
}
}
9
How is 0/1 Knapsack different from fractional knapsack?
| Aspect | 0/1 Knapsack | Fractional Knapsack |
|---|---|---|
| Selection | Item taken fully or not at all | Can take a fraction of an item |
| Algorithm | Dynamic programming | Greedy (sort by value/weight ratio) |
| Time | O(N * C) pseudo-polynomial | O(N log N) for sorting |
| Optimal guarantee | Always optimal | Always optimal |
| Use case | Loan deals (fund fully or skip) | Buying partial shares of a stock |
package com.bank.dsa;
import java.util.Arrays;
public class FractionalKnapsack {
public static double maxValue(int[] weight, int[] value, int capacity) {
int n = weight.length;
Integer[] idx = new Integer[n];
for (int i = 0; i < n; i++) idx[i] = i;
Arrays.sort(idx, (a, b) -> Double.compare(
(double) value[b] / weight[b], (double) value[a] / weight[a]));
double total = 0;
int remaining = capacity;
for (int i : idx) {
if (remaining == 0) break;
int take = Math.min(weight[i], remaining);
total += (double) value[i] * take / weight[i];
remaining -= take;
}
return total;
}
public static void main(String[] args) {
System.out.printf("Fractional: %.2f%n",
maxValue(new int[]{1, 3, 4, 5}, new int[]{1, 4, 5, 7}, 7));
}
}
Fractional: 11.33
What are common mistakes?
The most common mistake is sweeping capacity upward in the 1D version, which silently turns it into unbounded knapsack.
// WRONG: upward sweep allows item reuse
for (int c = weight[i]; c <= capacity; c++)
dp[c] = Math.max(dp[c], profit[i] + dp[c - weight[i]]);
// CORRECT: downward sweep ensures each item used once
for (int c = capacity; c >= weight[i]; c--)
dp[c] = Math.max(dp[c], profit[i] + dp[c - weight[i]]);
Another mistake is using 1-based item indexing in the profit and weight arrays without adjusting the array access, causing ArrayIndexOutOfBoundsException.
What are the edge cases?
When all items are heavier than the capacity, the answer is zero. When capacity is zero, the answer is zero. When a single item fits, the answer is that item's profit.
package com.bank.dsa;
public class KnapsackEdgeCases {
public static void main(String[] args) {
System.out.println(KnapsackOneRow.maxProfit(new int[]{10}, new int[]{5}, 3)); // 0
System.out.println(KnapsackOneRow.maxProfit(new int[]{3}, new int[]{5}, 3)); // 5
System.out.println(KnapsackOneRow.maxProfit(new int[]{}, new int[]{}, 10)); // 0
}
}
0
5
0
What should a senior engineer know?
A senior engineer should know that 0/1 Knapsack is NP-hard in general, and the O(N * C) algorithm is pseudo-polynomial because it depends on the numeric value of C. When C is enormous, the meet-in-the-middle approach splits items into two halves, enumerates all subsets of each in O(2^(N/2)), and combines them.
The pattern extends to multi-dimensional knapsacks (multiple constraints like weight and volume), which add dimensions to the DP table. It also connects to branch-and-bound solvers used in operations research for real-world optimisation.
In Java, bitset tricks can speed up subset-sum variants of knapsack. Using BitSet and shifting, you can process all capacities in parallel with a single bitwise OR operation per item.
Visual Overview
0/1 Knapsack Pattern: Include or Exclude
──────────────────────────────────────────
┌──────────┐
│ Item i │
│ w=3 v=4 │
└────┬─────┘
│
┌─────────┴─────────┐
│ │
┌─────▼──────┐ ┌──────▼──────┐
│ EXCLUDE │ │ INCLUDE │
│ dp[i-1][c]│ │ v + dp[i-1]│
│ │ │ [c - w] │
└─────┬──────┘ └──────┬──────┘
│ │
└─────────┬─────────┘
│
max(exclude, include)
Space Optimisation:
┌────────────────────────────────┐
│ Single row dp[0..C] │
│ Sweep: c = C → C-1 → ... → w │
│ dp[c] = max(dp[c], v+dp[c-w])│
└────────────────────────────────┘
Key Takeaway
The 0/1 Knapsack pattern is one of the most important dynamic programming patterns for interviews. Every item presents a binary choice: include it or skip it, under a shared capacity constraint. The 2D recurrence says the best value using the first i items at capacity c is the maximum of excluding the item (taking the value from the row above) and including it when it fits (adding its profit to the row above at the reduced capacity).
The space optimisation collapses the table to a single row swept from high capacity to low. The downward sweep is the correctness lever: it ensures dp[c - weight] still reflects the previous item's best value, enforcing the use-once rule. Sweeping upward would allow item reuse and silently solve unbounded knapsack instead.
At the National Bank of India, Rajesh used this pattern to select investment products for customers within a fixed budget, each product either fully purchased or skipped, maximising expected returns. The IT team also used it to select infrastructure upgrades within an annual budget. The pattern appears constantly in resource allocation, scheduling, and selection problems.
The senior-level detail is that the complexity is pseudo-polynomial: O(N * C) depends on the numeric capacity, not its bit length, which is why knapsack is NP-hard in general but tractable for practical capacity sizes.
Remember one sentence: for each item choose include or skip, sweep capacity downward in the 1D form, and the maximum value sits at dp[capacity].
---