0/1 Knapsack

13
0

Problem Statement

Two equal-length arrays weights and values describe available items. Entries at the same index form one item with a weight and a value. A non-negative integer capacity gives the maximum total weight supported by a knapsack.

Choose a subset of items without exceeding capacity. Every indexed item may be selected once or skipped. Return the maximum total value among all valid subsets. An empty selection is allowed and contributes value 0.

Example 1

Input: weights = [1, 2, 4, 5], values = [5, 4, 8, 6], capacity = 5
Output: 13
Explanation: Selecting weights 1 and 4 uses the complete capacity and gives value 5 + 8 = 13, the largest value among all valid subsets.

Example 2

Input: weights = [4, 5], values = [7, 8], capacity = 3
Output: 0
Explanation: Every item is heavier than the knapsack capacity, so the empty selection gives the maximum valid value.

Recursion

A single item has only two legal outcomes: stay outside the knapsack or enter the knapsack once. Following both choices for every item covers every possible subset, so recursion matches the binary decision pattern naturally.

State solve(index, remainingCapacity) represents the best value from indices 0 through index under the remaining weight limit. The public method starts from the final index because the full item range must remain available before the first decision. A take branch reduces capacity and moves to the preceding index, while a skip branch only moves to the preceding index.

Algorithm

  • Begin with solve(n - 1, capacity), because the final index and full capacity together represent every available item and the complete weight limit.

  • Handle index 0 directly, returning the first value only after the first weight fits so the smallest subproblem respects the capacity.

  • Explore a skip branch at index - 1 with unchanged capacity, because leaving the current item preserves the complete remaining limit.

  • Keep the take value unavailable at first, so an overweight item can never become part of a valid maximum.

  • Explore a take branch only after the current weight fits, reducing the capacity and moving backward to prevent a second use of the same item.

  • Compare the take and skip values, because the larger branch gives the best valid subset for the current state.

  • Return the value from the initial state, because all take-or-skip combinations have been considered along the recursive tree.

Dry Run

Diagram 1
1 / 2

Diagram 1

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
// Finds the best value through one item index.
int solve(
int index,
int remainingCapacity,
vector<int>& weights,
vector<int>& values
) {
// The first item works only after fitting.
if (index == 0) {
// Enough capacity allows the first item.
if (weights[0] <= remainingCapacity) {
return values[0];
}
return 0;
}
// Skipping preserves the remaining capacity.
int notTake = solve(
index - 1,
remainingCapacity,
weights,
values
);
// An invalid take cannot win the comparison.
int take = INT_MIN;
// A fitting item creates the take branch.
if (weights[index] <= remainingCapacity) {
// Taking adds value and reduces capacity.
take = values[index] + solve(
index - 1,
remainingCapacity - weights[index],
weights,
values
);
}
// The better branch gives the state answer.
return max(notTake, take);
}
public:
// Returns the maximum value within capacity.
int knapsack(
vector<int>& weights,
vector<int>& values,
int capacity
) {
// No item leaves only the empty selection.
if (weights.empty()) {
return 0;
}
int n = weights.size();
// The final index exposes every item.
return solve(n - 1, capacity, weights, values);
}
};
// Driver code
int main() {
vector<int> weights = {1, 2, 4, 5};
vector<int> values = {5, 4, 8, 6};
int capacity = 5;
Solution obj;
cout << obj.knapsack(weights, values, capacity) << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(2N), where N is the number of items, because every item can create a take branch and a skip branch across a recursion depth of N.

Space Complexity: O(N), because the deepest recursive path stores one call for every item index.

Note: Direct recursion may fail for large input values. Repeated subproblems create exponential work, so an online judge may report Time Limit Exceeded.

Memoization

Direct recursion revisits identical pairs of item index and remaining capacity through different earlier choices. Every repeated pair produces the same best value, so rebuilding an already explored subtree adds no useful information.

A two-dimensional array named dp stores each finished state. A stored answer returns immediately during a later visit, while the original take-or-skip decision and recursive state remain unchanged.

Algorithm

  • Begin with the same state solve(n - 1, capacity), because memoization must preserve the recursive meaning and the complete starting problem.

  • Create dp with n rows and capacity + 1 columns filled with -1, so every untouched cell marks an uncalculated state.

  • Handle index 0 before cache access, because the smallest subproblem depends only on whether the first weight fits.

  • Return dp[index][remainingCapacity] after a stored value appears, avoiding another traversal of the same recursive subtree.

  • Compute skip and fitting take branches exactly as recursion does, so cached states preserve the original 0/1 decisions.

  • Store the larger branch value in dp, because every future visit to the same state needs the same optimal result.

  • Return the cached value for the initial state, because the complete item range and capacity define the requested maximum.

Dry Run

Diagram 1
1 / 2

Diagram 1

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
// Finds and stores one knapsack state.
int solve(
int index,
int remainingCapacity,
vector<int>& weights,
vector<int>& values,
vector<vector<int>>& dp
) {
// The first item works only after fitting.
if (index == 0) {
// Enough capacity allows the first item.
if (weights[0] <= remainingCapacity) {
return values[0];
}
return 0;
}
// A stored answer avoids repeated recursion.
if (dp[index][remainingCapacity] != -1) {
return dp[index][remainingCapacity];
}
// Skipping preserves the remaining capacity.
int notTake = solve(
index - 1,
remainingCapacity,
weights,
values,
dp
);
// An invalid take cannot win the comparison.
int take = INT_MIN;
// A fitting item creates the take branch.
if (weights[index] <= remainingCapacity) {
// Taking adds value and reduces capacity.
take = values[index] + solve(
index - 1,
remainingCapacity - weights[index],
weights,
values,
dp
);
}
// Cache the better branch for later visits.
dp[index][remainingCapacity] = max(notTake, take);
return dp[index][remainingCapacity];
}
public:
// Returns the maximum value within capacity.
int knapsack(
vector<int>& weights,
vector<int>& values,
int capacity
) {
// No item leaves only the empty selection.
if (weights.empty()) {
return 0;
}
int n = weights.size();
// Negative cells mark uncalculated states.
vector<vector<int>> dp(
n,
vector<int>(capacity + 1, -1)
);
// The final index exposes every item.
return solve(
n - 1,
capacity,
weights,
values,
dp
);
}
};
// Driver code
int main() {
vector<int> weights = {1, 2, 4, 5};
vector<int> values = {5, 4, 8, 6};
int capacity = 5;
Solution obj;
cout << obj.knapsack(weights, values, capacity) << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(N × capacity), where N is the number of items, because at most N × (capacity + 1) states are evaluated once and each state performs constant work.

Space Complexity: O(N × capacity + N), because the dp table stores all item-capacity states and the recursion stack can contain at most N calls.

Tabulation

Memoization still depends on recursive calls to discover states. Tabulation arranges the same states in a table and fills smaller item ranges first, removing call-stack work while preserving every take-or-skip transition.

Row index stores answers using items from 0 through index. The base row records the first item wherever the capacity can hold the first weight. Every later row reads only the preceding row, so both branch answers are ready before a current cell is filled.

Algorithm

  • Begin with an n by capacity + 1 array named dp, because each recursive pair of item index and capacity needs one bottom-up cell.

  • Fill the first row with values[0] from weights[0] through capacity, so the base row matches the recursive first-item decision.

  • Move through item indices from 1 to n - 1, ensuring the preceding row is complete before any current-row transition begins.

  • Read dp[index - 1][currentCapacity] for the skip value, because skipping preserves capacity and removes the current item from consideration.

  • Keep the take value unavailable until the current weight fits, preventing an overweight choice from affecting the maximum.

  • Add the current value to dp[index - 1][currentCapacity - weights[index]] after a fit, so taking uses only preceding items.

  • Store the larger take-or-skip value and return dp[n - 1][capacity], because the final cell represents every item under the full limit.

Dry Run

0/1 Knapsack Tabulation

0/1 Knapsack Tabulation

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Returns the maximum value within capacity.
int knapsack(
vector<int>& weights,
vector<int>& values,
int capacity
) {
// No item leaves only the empty selection.
if (weights.empty()) {
return 0;
}
int n = weights.size();
// Each cell stores one recursive state.
vector<vector<int>> dp(
n,
vector<int>(capacity + 1, 0)
);
// The first item fills every fitting capacity.
for (
int currentCapacity = weights[0];
currentCapacity <= capacity;
currentCapacity++
) {
dp[0][currentCapacity] = values[0];
}
// Later rows use completed preceding rows.
for (int index = 1; index < n; index++) {
// Every capacity represents one state.
for (
int currentCapacity = 0;
currentCapacity <= capacity;
currentCapacity++
) {
// Skipping reads the preceding item row.
int notTake = dp[index - 1][currentCapacity];
// An invalid take cannot win the comparison.
int take = INT_MIN;
// A fitting item creates the take value.
if (weights[index] <= currentCapacity) {
// Taking reads only the preceding row.
take = values[index]
+ dp[index - 1][
currentCapacity - weights[index]
];
}
// The better choice fills the current cell.
dp[index][currentCapacity] = max(
notTake,
take
);
}
}
// The final cell covers all items and capacity.
return dp[n - 1][capacity];
}
};
// Driver code
int main() {
vector<int> weights = {1, 2, 4, 5};
vector<int> values = {5, 4, 8, 6};
int capacity = 5;
Solution obj;
cout << obj.knapsack(weights, values, capacity) << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(N × capacity), where N is the number of items, because every one of the N × (capacity + 1) table cells performs constant work.

Space Complexity: O(N × capacity), because the two-dimensional dp table stores one answer for every item-capacity pair, and iterative tabulation eliminates recursion stack space.

Space Optimization

Every tabulation row reads only values from the preceding item row. A single array can preserve the required older values by scanning capacities from the full limit down to the current item weight.

For each fitting capacity, current adds the current item value to the untouched smaller-capacity answer. Descending updates shift larger capacity states first, so the smaller state still belongs to the preceding item stage and one indexed item cannot enter twice.

Algorithm

  • Begin with a one-dimensional array named dp of size capacity + 1, because only one value per capacity must survive between item stages.

  • Fill capacities from weights[0] through capacity with values[0], so the array starts with the same first-item base row as tabulation.

  • Move through later items one at a time, ensuring every array update belongs to a single indexed item stage.

  • Scan currentCapacity downward from capacity to weights[index], because descending order preserves the smaller state from the preceding item stage.

  • Calculate current as the current item value plus dp[currentCapacity - weights[index]], so the take choice uses remaining capacity from older data.

  • Compare dp[currentCapacity] with current, preserving the better skip-or-take value without creating a second array.

  • Return dp[capacity], because the final item stage leaves the best value for the complete capacity in the last cell.

Dry Run

0/1 Knapsack Space Optimization

0/1 Knapsack Space Optimization

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Returns the maximum value within capacity.
int knapsack(
vector<int>& weights,
vector<int>& values,
int capacity
) {
// No item leaves only the empty selection.
if (weights.empty()) {
return 0;
}
int n = weights.size();
// One cell survives for every capacity.
vector<int> dp(capacity + 1, 0);
// The first item fills every fitting capacity.
for (
int currentCapacity = weights[0];
currentCapacity <= capacity;
currentCapacity++
) {
dp[currentCapacity] = values[0];
}
// Later items reuse the same capacity array.
for (int index = 1; index < n; index++) {
// Descending order prevents item reuse.
for (
int currentCapacity = capacity;
currentCapacity >= weights[index];
currentCapacity--
) {
// Current value uses an older smaller state.
int current = values[index]
+ dp[currentCapacity - weights[index]];
// Descending order shifts capacities safely.
dp[currentCapacity] = max(
dp[currentCapacity],
current
);
}
}
// The final cell represents the full capacity.
return dp[capacity];
}
};
// Driver code
int main() {
vector<int> weights = {1, 2, 4, 5};
vector<int> values = {5, 4, 8, 6};
int capacity = 5;
Solution obj;
cout << obj.knapsack(weights, values, capacity) << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(N × capacity), where N is the number of items, because every item scans at most capacity + 1 states and each state performs constant work.

Space Complexity: O(capacity), because a single dp array stores the best value for each capacity and no recursion stack is used.

Interview follow-up Questions

No. Every index represents one available item, so a second selection would change the problem into unbounded knapsack.

Dynamic ProgrammingTCS NQT

Read Similar Blogs

Comments0