0/1 Knapsack Problem Code Implementations
Complete 0/1 Knapsack Problem code implementations in C++, Python, Java, and JavaScript with time and space complexity analysis on AntInLoop.
Read 0/1 Knapsack Problem Guide ยท Launch Interactive Visualizer
C++ Implementation
// 0/1 Knapsack Problem Implementation in C++
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
class Knapsack01 {
public:
static int knapsack01(const std::vector<int>& weights, const std::vector<int>& values, int capacity) {
int n = weights.size();
std::vector<std::vector<int>> dp(n + 1, std::vector<int>(capacity + 1, 0));
// Build table dp[][] in bottom-up manner
for (int i = 1; i <= n; i++) {
for (int w = 0; w <= capacity; w++) {
if (weights[i - 1] <= w) {
// Take the item
dp[i][w] = std::max(
dp[i - 1][w], // Don't take the item
dp[i - 1][w - weights[i - 1]] + values[i - 1] // Take the item
);
} else {
// Can't take the item
dp[i][w] = dp[i - 1][w];
}
}
}
return dp[n][capacity];
}
// Space-optimized version using 1D array
static int knapsack01Optimized(const std::vector<int>& weights, const std::vector<int>& values, int capacity) {
int n = weights.size();
std::vector<int> dp(capacity + 1, 0);
for (int i = 0; i < n; i++) {
for (int w = capacity; w >= weights[i]; w--) {
dp[w] = std::max(dp[w], dp[w - weights[i]] + values[i]);
}
}
return dp[capacity];
}
// Knapsack with item tracking
struct KnapsackResult {
int maxValue;
std::vector<int> selectedItems;
KnapsackResult(int maxVal, const std::vector<int>& items)
: maxValue(maxVal), selectedItems(items) {}
};
static KnapsackResult knapsack01WithItems(const std::vector<int>& weights, const std::vector<int>& values, int capacity) {
int n = weights.size();
std::vector<std::vector<int>> dp(n + 1, std::vector<int>(capacity + 1, 0));
std::vector<std::vector<bool>> selected(n + 1, std::vector<bool>(capacity + 1, false));
for (int i = 1; i <= n; i++) {
for (int w = 0; w <= capacity; w++) {
if (weights[i - 1] <= w) {
int takeValue = dp[i - 1][w - weights[i - 1]] + values[i - 1];
int skipValue = dp[i - 1][w];
if (takeValue > skipValue) {
dp[i][w] = takeValue;
selected[i][w] = true;
} else {
dp[i][w] = skipValue;
}
} else {
dp[i][w] = dp[i - 1][w];
}
}
}
// Reconstruct the solution
std::vector<int> items;
int i = n, w = capacity;
while (i > 0 && w > 0) {
if (selected[i][w]) {
items.push_back(i - 1);
w -= weights[i - 1];
}
i--;
}
std::reverse(items.begin(), items.end());
return KnapsackResult(dp[n][capacity], items);
}
// Memoization approach (top-down)
static int knapsack01Memo(const std::vector<int>& weights, const std::vector<int>& values, int capacity) {
int n = weights.size();
std::unordered_map<std::string, int> memo;
return solveMemo(weights, values, n, capacity, memo);
}
private:
static int solveMemo(const std::vector<int>& weights, const std::vector<int>& values,
int i, int w, std::unordered_map<std::string, int>& memo) {
if (i == 0 || w == 0) {
return 0;
}
std::string key = std::to_string(i) + "," + std::to_string(w);
if (memo.find(key) != memo.end()) {
return memo[key];
}
int result;
if (weights[i - 1] <= w) {
result = std::max(
solveMemo(weights, values, i - 1, w, memo), // Don't take
solveMemo(weights, values, i - 1, w - weights[i - 1], memo) + values[i - 1] // Take
);
} else {
result = solveMemo(weights, values, i - 1, w, memo);
}
memo[key] = result;
return result;
}
public:
// Fractional Knapsack (Greedy approach for comparison)
static double fractionalKnapsack(const std::vector<int>& weights, const std::vector<int>& values, int capacity) {
int n = weights.size();
std::vector<std::pair<double, int>> items; // [ratio, index]
for (int i = 0; i < n; i++) {
items.push_back({(double)values[i] / weights[i], i});
}
std::sort(items.rbegin(), items.rend()); // Sort by ratio descending
double totalValue = 0;
int remainingCapacity = capacity;
for (const auto& item : items) {
int index = item.second;
if (remainingCapacity >= weights[index]) {
totalValue += values[index];
remainingCapacity -= weights[index];
} else {
totalValue += item.first * remainingCapacity;
break;
}
}
return totalValue;
}
};JAVA Implementation
// 0/1 Knapsack Problem Implementation in Java
public class Knapsack01 {
public static int knapsack01(int[] weights, int[] values, int capacity) {
int n = weights.length;
int[][] dp = new int[n + 1][capacity + 1];
// Build table dp[][] in bottom-up manner
for (int i = 1; i <= n; i++) {
for (int w = 0; w <= capacity; w++) {
if (weights[i - 1] <= w) {
// Take the item
dp[i][w] = Math.max(
dp[i - 1][w], // Don't take the item
dp[i - 1][w - weights[i - 1]] + values[i - 1] // Take the item
);
} else {
// Can't take the item
dp[i][w] = dp[i - 1][w];
}
}
}
return dp[n][capacity];
}
// Space-optimized version using 1D array
public static int knapsack01Optimized(int[] weights, int[] values, int capacity) {
int n = weights.length;
int[] dp = new int[capacity + 1];
for (int i = 0; i < n; i++) {
for (int w = capacity; w >= weights[i]; w--) {
dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
}
}
return dp[capacity];
}
// Knapsack with item tracking
public static class KnapsackResult {
public int maxValue;
public int[] selectedItems;
public KnapsackResult(int maxValue, int[] selectedItems) {
this.maxValue = maxValue;
this.selectedItems = selectedItems;
}
}
public static KnapsackResult knapsack01WithItems(int[] weights, int[] values, int capacity) {
int n = weights.length;
int[][] dp = new int[n + 1][capacity + 1];
boolean[][] selected = new boolean[n + 1][capacity + 1];
for (int i = 1; i <= n; i++) {
for (int w = 0; w <= capacity; w++) {
if (weights[i - 1] <= w) {
int takeValue = dp[i - 1][w - weights[i - 1]] + values[i - 1];
int skipValue = dp[i - 1][w];
if (takeValue > skipValue) {
dp[i][w] = takeValue;
selected[i][w] = true;
} else {
dp[i][w] = skipValue;
}
} else {
dp[i][w] = dp[i - 1][w];
}
}
}
// Reconstruct the solution
java.util.List<Integer> items = new java.util.ArrayList<>();
int i = n, w = capacity;
while (i > 0 && w > 0) {
if (selected[i][w]) {
items.add(i - 1);
w -= weights[i - 1];
}
i--;
}
java.util.Collections.reverse(items);
int[] selectedItems = items.stream().mapToInt(Integer::intValue).toArray();
return new KnapsackResult(dp[n][capacity], selectedItems);
}
// Memoization approach (top-down)
public static int knapsack01Memo(int[] weights, int[] values, int capacity) {
int n = weights.length;
java.util.Map<String, Integer> memo = new java.util.HashMap<>();
return solveMemo(weights, values, n, capacity, memo);
}
private static int solveMemo(int[] weights, int[] values, int i, int w, java.util.Map<String, Integer> memo) {
if (i == 0 || w == 0) {
return 0;
}
String key = i + "," + w;
if (memo.containsKey(key)) {
return memo.get(key);
}
int result;
if (weights[i - 1] <= w) {
result = Math.max(
solveMemo(weights, values, i - 1, w, memo), // Don't take
solveMemo(weights, values, i - 1, w - weights[i - 1], memo) + values[i - 1] // Take
);
} else {
result = solveMemo(weights, values, i - 1, w, memo);
}
memo.put(key, result);
return result;
}
// Fractional Knapsack (Greedy approach for comparison)
public static double fractionalKnapsack(int[] weights, int[] values, int capacity) {
int n = weights.length;
double[][] items = new double[n][3]; // [ratio, weight, value]
for (int i = 0; i < n; i++) {
items[i][0] = (double) values[i] / weights[i];
items[i][1] = weights[i];
items[i][2] = values[i];
}
java.util.Arrays.sort(items, (a, b) -> Double.compare(b[0], a[0]));
double totalValue = 0;
int remainingCapacity = capacity;
for (double[] item : items) {
if (remainingCapacity >= item[1]) {
totalValue += item[2];
remainingCapacity -= item[1];
} else {
totalValue += item[0] * remainingCapacity;
break;
}
}
return totalValue;
}
}JAVASCRIPT Implementation
// 0/1 Knapsack Problem Implementation in JavaScript
function knapsack01(weights, values, capacity) {
const n = weights.length;
const dp = Array(n + 1).fill().map(() => Array(capacity + 1).fill(0));
// Build table dp[][] in bottom-up manner
for (let i = 1; i <= n; i++) {
for (let w = 0; w <= capacity; w++) {
if (weights[i - 1] <= w) {
// Take the item
dp[i][w] = Math.max(
dp[i - 1][w], // Don't take the item
dp[i - 1][w - weights[i - 1]] + values[i - 1] // Take the item
);
} else {
// Can't take the item
dp[i][w] = dp[i - 1][w];
}
}
}
return dp[n][capacity];
}
// Space-optimized version using 1D array
function knapsack01Optimized(weights, values, capacity) {
const n = weights.length;
const dp = Array(capacity + 1).fill(0);
for (let i = 0; i < n; i++) {
for (let w = capacity; w >= weights[i]; w--) {
dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
}
}
return dp[capacity];
}
// Knapsack with item tracking
function knapsack01WithItems(weights, values, capacity) {
const n = weights.length;
const dp = Array(n + 1).fill().map(() => Array(capacity + 1).fill(0));
const selected = Array(n + 1).fill().map(() => Array(capacity + 1).fill(false));
for (let i = 1; i <= n; i++) {
for (let w = 0; w <= capacity; w++) {
if (weights[i - 1] <= w) {
const takeValue = dp[i - 1][w - weights[i - 1]] + values[i - 1];
const skipValue = dp[i - 1][w];
if (takeValue > skipValue) {
dp[i][w] = takeValue;
selected[i][w] = true;
} else {
dp[i][w] = skipValue;
}
} else {
dp[i][w] = dp[i - 1][w];
}
}
}
// Reconstruct the solution
const items = [];
let i = n, w = capacity;
while (i > 0 && w > 0) {
if (selected[i][w]) {
items.push(i - 1);
w -= weights[i - 1];
}
i--;
}
return {
maxValue: dp[n][capacity],
selectedItems: items.reverse()
};
}
// Fractional Knapsack (Greedy approach for comparison)
function fractionalKnapsack(weights, values, capacity) {
const items = weights.map((weight, index) => ({
weight,
value: values[index],
ratio: values[index] / weight
}));
items.sort((a, b) => b.ratio - a.ratio);
let totalValue = 0;
let remainingCapacity = capacity;
for (const item of items) {
if (remainingCapacity >= item.weight) {
totalValue += item.value;
remainingCapacity -= item.weight;
} else {
totalValue += item.ratio * remainingCapacity;
break;
}
}
return totalValue;
}PYTHON Implementation
# 0/1 Knapsack Problem Implementation in Python
def knapsack_01(weights, values, capacity):
n = len(weights)
dp = [[0] * (capacity + 1) for _ in range(n + 1)]
# Build table dp[][] in bottom-up manner
for i in range(1, n + 1):
for w in range(capacity + 1):
if weights[i - 1] <= w:
# Take the item
dp[i][w] = max(
dp[i - 1][w], # Don't take the item
dp[i - 1][w - weights[i - 1]] + values[i - 1] # Take the item
)
else:
# Can't take the item
dp[i][w] = dp[i - 1][w]
return dp[n][capacity]
# Space-optimized version using 1D array
def knapsack_01_optimized(weights, values, capacity):
n = len(weights)
dp = [0] * (capacity + 1)
for i in range(n):
for w in range(capacity, weights[i] - 1, -1):
dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
return dp[capacity]
# Knapsack with item tracking
def knapsack_01_with_items(weights, values, capacity):
n = len(weights)
dp = [[0] * (capacity + 1) for _ in range(n + 1)]
selected = [[False] * (capacity + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for w in range(capacity + 1):
if weights[i - 1] <= w:
take_value = dp[i - 1][w - weights[i - 1]] + values[i - 1]
skip_value = dp[i - 1][w]
if take_value > skip_value:
dp[i][w] = take_value
selected[i][w] = True
else:
dp[i][w] = skip_value
else:
dp[i][w] = dp[i - 1][w]
# Reconstruct the solution
items = []
i, w = n, capacity
while i > 0 and w > 0:
if selected[i][w]:
items.append(i - 1)
w -= weights[i - 1]
i -= 1
return {
'max_value': dp[n][capacity],
'selected_items': items[::-1]
}
# Fractional Knapsack (Greedy approach for comparison)
def fractional_knapsack(weights, values, capacity):
items = [(values[i] / weights[i], weights[i], values[i]) for i in range(len(weights))]
items.sort(reverse=True) # Sort by value/weight ratio
total_value = 0
remaining_capacity = capacity
for ratio, weight, value in items:
if remaining_capacity >= weight:
total_value += value
remaining_capacity -= weight
else:
total_value += ratio * remaining_capacity
break
return total_value
# Memoization approach (top-down)
def knapsack_01_memo(weights, values, capacity):
n = len(weights)
memo = {}
def solve(i, w):
if i == 0 or w == 0:
return 0
if (i, w) in memo:
return memo[(i, w)]
if weights[i - 1] <= w:
result = max(
solve(i - 1, w), # Don't take
solve(i - 1, w - weights[i - 1]) + values[i - 1] # Take
)
else:
result = solve(i - 1, w)
memo[(i, w)] = result
return result
return solve(n, capacity)