0-1 Knapsack
In this page:
Problem Idea
In the 0-1 knapsack problem, you're choosing which items to pack into a bag with a fixed weight capacity to maximize total value, but each item is either fully taken or fully left behind — there's no way to take part of one or take it twice.
Example: Problem Idea
#include <iostream>
using namespace std;
int main() {
int weights[] = {2,3,4}, values[] = {3,4,5}, capacity = 5;
cout << "Choose subset of items, weight <= " << capacity << ", each item fully taken or fully left";
return 0;
}public class Main {
public static void main(String[] args) {
int[] weights = {2,3,4}, values = {3,4,5};
int capacity = 5;
System.out.println("Choose subset of items, weight <= " + capacity + ", each item fully taken or fully left");
}
}weights, values, capacity = [2,3,4], [3,4,5], 5
print(f"Choose subset of items, weight <= {capacity}, each item fully taken or fully left")#include <stdio.h>
int main() {
int weights[] = {2,3,4}, values[] = {3,4,5}, capacity = 5;
printf("Choose subset of items, weight <= %d, each item fully taken or fully left", capacity);
return 0;
}Login to try C/C++/Java code in the editor
DP State
dp[i][w] represents the best total value achievable using only the first i items with a knapsack of capacity w, so building this table item by item eventually reveals the best possible value for every capacity you might need.
Example: DP State
#include <iostream>
using namespace std;
int main() {
int dp[4][6] = {0};
cout << "dp[i][w] = best value using first i items with capacity w; dp[3][5] is the final answer slot";
return 0;
}public class Main {
public static void main(String[] args) {
int[][] dp = new int[4][6];
System.out.println("dp[i][w] = best value using first i items with capacity w; dp[3][5] is the final answer slot");
}
}dp = [[0]*6 for _ in range(4)]
print("dp[i][w] = best value using first i items with capacity w; dp[3][5] is the final answer slot")#include <stdio.h>
int main() {
int dp[4][6] = {0};
printf("dp[i][w] = best value using first i items with capacity w; dp[3][5] is the final answer slot");
return 0;
}Login to try C/C++/Java code in the editor
Transition
For each item you have exactly two choices: skip it and keep the best value already found without it, or take it (if it fits) and add its value to the best result for the remaining capacity — the DP transition simply takes the better of these two options.
Example: Transition
#include <iostream>
using namespace std;
int main() {
int weights[] = {2,3,4}, values[] = {3,4,5}, capacity = 5, n = 3;
int dp[4][6] = {0};
for (int i = 1; i <= n; i++)
for (int w = 0; w <= capacity; w++) {
dp[i][w] = dp[i-1][w];
if (weights[i-1] <= w) dp[i][w] = max(dp[i][w], dp[i-1][w-weights[i-1]] + values[i-1]);
}
cout << "Best value with capacity " << capacity << ": " << dp[n][capacity];
return 0;
}public class Main {
public static void main(String[] args) {
int[] weights = {2,3,4}, values = {3,4,5};
int capacity = 5, n = 3;
int[][] dp = new int[4][6];
for (int i = 1; i <= n; i++)
for (int w = 0; w <= capacity; w++) {
dp[i][w] = dp[i-1][w];
if (weights[i-1] <= w) dp[i][w] = Math.max(dp[i][w], dp[i-1][w-weights[i-1]] + values[i-1]);
}
System.out.println("Best value with capacity " + capacity + ": " + dp[n][capacity]);
}
}weights, values, capacity, n = [2,3,4], [3,4,5], 5, 3
dp = [[0]*(capacity+1) for _ in range(n+1)]
for i in range(1, n+1):
for w in range(capacity+1):
dp[i][w] = dp[i-1][w]
if weights[i-1] <= w:
dp[i][w] = max(dp[i][w], dp[i-1][w-weights[i-1]] + values[i-1])
print(f"Best value with capacity {capacity}: {dp[n][capacity]}")#include <stdio.h>
int main() {
int weights[] = {2,3,4}, values[] = {3,4,5}, capacity = 5, n = 3;
int dp[4][6] = {0};
for (int i = 1; i <= n; i++)
for (int w = 0; w <= capacity; w++) {
dp[i][w] = dp[i-1][w];
if (weights[i-1] <= w && dp[i-1][w-weights[i-1]] + values[i-1] > dp[i][w])
dp[i][w] = dp[i-1][w-weights[i-1]] + values[i-1];
}
printf("Best value with capacity %d: %d", capacity, dp[n][capacity]);
return 0;
}Login to try C/C++/Java code in the editor
Space Optimization
Since dp[i][w] only ever depends on the previous row (dp[i-1][...]), you can collapse the 2D table into a single 1D array, as long as you update it from high capacity down to low capacity so you don't accidentally reuse an item twice.
Example: Space Optimization
#include <iostream>
using namespace std;
int main() {
int weights[] = {2,3,4}, values[] = {3,4,5}, capacity = 5;
int dp[6] = {0};
for (int i = 0; i < 3; i++)
for (int w = capacity; w >= weights[i]; w--)
dp[w] = max(dp[w], dp[w-weights[i]] + values[i]);
cout << "1D array updated high-to-low, best value: " << dp[capacity];
return 0;
}public class Main {
public static void main(String[] args) {
int[] weights = {2,3,4}, values = {3,4,5};
int capacity = 5;
int[] dp = new int[6];
for (int i = 0; i < 3; i++)
for (int w = capacity; w >= weights[i]; w--)
dp[w] = Math.max(dp[w], dp[w-weights[i]] + values[i]);
System.out.println("1D array updated high-to-low, best value: " + dp[capacity]);
}
}weights, values, capacity = [2,3,4], [3,4,5], 5
dp = [0]*(capacity+1)
for i in range(3):
for w in range(capacity, weights[i]-1, -1):
dp[w] = max(dp[w], dp[w-weights[i]] + values[i])
print("1D array updated high-to-low, best value:", dp[capacity])#include <stdio.h>
int main() {
int weights[] = {2,3,4}, values[] = {3,4,5}, capacity = 5;
int dp[6] = {0};
for (int i = 0; i < 3; i++)
for (int w = capacity; w >= weights[i]; w--)
if (dp[w-weights[i]] + values[i] > dp[w]) dp[w] = dp[w-weights[i]] + values[i];
printf("1D array updated high-to-low, best value: %d", dp[capacity]);
return 0;
}Login to try C/C++/Java code in the editor
Practice
0-1 knapsack is the classic example for 'choose or don't choose' optimization problems, and the same DP shape reappears whenever you're selecting a subset of items under a hard constraint.
Example: Practice
#include <iostream>
using namespace std;
int main() {
cout << "Same DP shape reappears anywhere you select a subset of items under a hard constraint";
return 0;
}public class Main {
public static void main(String[] args) {
System.out.println("Same DP shape reappears anywhere you select a subset of items under a hard constraint");
}
}print("Same DP shape reappears anywhere you select a subset of items under a hard constraint")#include <stdio.h>
int main() {
printf("Same DP shape reappears anywhere you select a subset of items under a hard constraint");
return 0;
}Login to try C/C++/Java code in the editor
Chapter Quiz — Complete all 12 topics to unlock
0/12 topics done
Complete these topics first: