AntInLoop

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)