fork download
copy 
  1. def knapsack_01_dp(values, weights, capacity):
  2.     """
  3.     0/1 Knapsack - Dynamic Programming solution
  4.  
  5.     Args:
  6.         values: List of item values [v1, v2, ..., vn]
  7.         weights: List of item weights [w1, w2, ..., wn]
  8.         capacity: Maximum weight capacity (W)
  9.  
  10.     Returns:
  11.         tuple: (max_value, selected_items)
  12.                - max_value: Maximum achievable value
  13.                - selected_items: List of indices of selected items
  14.  
  15.     Time Complexity: O(n * W)
  16.     Space Complexity: O(n * W)
  17.     """
  18.     n = len(values)
  19.  
  20.     # Create DP table: dp[i][w] = max value using first i items with capacity w
  21.     dp = [[0] * (capacity + 1) for _ in range(n + 1)]
  22.  
  23.     # Build table bottom-up
  24.     for i in range(1, n + 1):
  25.         for w in range(capacity + 1):
  26.             if weights[i-1] <= w:
  27.                 # Option 1: Take the item
  28.                 take_value = dp[i-1][w - weights[i-1]] + values[i-1]
  29.                 # Option 2: Skip the item
  30.                 skip_value = dp[i-1][w]
  31.                 dp[i][w] = max(take_value, skip_value)
  32.             else:
  33.                 # Can't take the item (too heavy)
  34.                 dp[i][w] = dp[i-1][w]
  35.  
  36.     # Reconstruct selected items (backtracking)
  37.     selected = []
  38.     w = capacity
  39.     for i in range(n, 0, -1):
  40.         if dp[i][w] != dp[i-1][w]:  # Item was taken
  41.             selected.append(i-1)
  42.             w -= weights[i-1]
  43.  
  44.     return dp[n][capacity], selected[::-1]
  45.  
  46.  
  47. def knapsack_01_dp_optimized(values, weights, capacity):
  48.     """
  49.     0/1 Knapsack - Space-optimized DP (1D array)
  50.  
  51.     Time Complexity: O(n * W)
  52.     Space Complexity: O(W)
  53.     """
  54.     n = len(values)
  55.     dp = [0] * (capacity + 1)
  56.  
  57.     for i in range(n):
  58.         # Iterate backwards to avoid overwriting
  59.         for w in range(capacity, weights[i] - 1, -1):
  60.             dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
  61.  
  62.     return dp[capacity]
  63.  
  64.  
  65. def knapsack_01_brute_force(values, weights, capacity):
  66.     """
  67.     0/1 Knapsack - Brute Force (for comparison)
  68.  
  69.     Time Complexity: O(2^n)
  70.     Space Complexity: O(n)
  71.     """
  72.     n = len(values)
  73.     max_value = 0
  74.     best_combo = []
  75.  
  76.     # Try all 2^n combinations
  77.     for i in range(1 << n):
  78.         current_weight = 0
  79.         current_value = 0
  80.         selected = []
  81.  
  82.         for j in range(n):
  83.             if i & (1 << j):  # Item j is selected
  84.                 current_weight += weights[j]
  85.                 current_value += values[j]
  86.                 selected.append(j)
  87.  
  88.         if current_weight <= capacity and current_value > max_value:
  89.             max_value = current_value
  90.             best_combo = selected
  91.  
  92.     return max_value, best_combo
  93.  
  94.  
  95. def print_solution(values, weights, capacity, max_value, selected_items):
  96.     """Pretty print the solution"""
  97.     print(f"\n{'='*50}")
  98.     print("0/1 KNAPSACK SOLUTION")
  99.     print(f"{'='*50}")
  100.     print(f"Items: {len(values)}")
  101.     print(f"Capacity: {capacity}")
  102.     print(f"Max Value: {max_value}")
  103.     print(f"Selected Items: {selected_items}")
  104.  
  105.     total_weight = sum(weights[i] for i in selected_items)
  106.     total_value = sum(values[i] for i in selected_items)
  107.  
  108.     print(f"Total Weight: {total_weight}")
  109.     print(f"Total Value: {total_value}")
  110.     print("\nItem Details:")
  111.     for i in selected_items:
  112.         print(f"  Item {i}: value={values[i]}, weight={weights[i]}")
  113.  
  114.  
  115. # ============= EXAMPLES =============
  116.  
  117. def run_examples():
  118.     """Run test cases"""
  119.  
  120.     # Example 1: Classic problem
  121.     print("\n" + "="*60)
  122.     print("EXAMPLE 1: Classic 0/1 Knapsack")
  123.     print("="*60)
  124.  
  125.     values = [60, 100, 120]
  126.     weights = [10, 20, 30]
  127.     capacity = 50
  128.  
  129.     max_val, selected = knapsack_01_dp(values, weights, capacity)
  130.     print_solution(values, weights, capacity, max_val, selected)
  131.  
  132.     # Compare with brute force
  133.     max_val_bf, selected_bf = knapsack_01_brute_force(values, weights, capacity)
  134.     print(f"\nBrute Force Result: {max_val_bf}")
  135.     print(f"Brute Force Selected: {selected_bf}")
  136.  
  137.     # Example 2: Larger problem
  138.     print("\n" + "="*60)
  139.     print("EXAMPLE 2: Larger Knapsack")
  140.     print("="*60)
  141.  
  142.     values = [20, 5, 10, 40, 15, 25]
  143.     weights = [1, 2, 3, 8, 7, 4]
  144.     capacity = 10
  145.  
  146.     max_val, selected = knapsack_01_dp(values, weights, capacity)
  147.     print_solution(values, weights, capacity, max_val, selected)
  148.  
  149.     # Example 3: Real-world scenario
  150.     print("\n" + "="*60)
  151.     print("EXAMPLE 3: Backpack Problem")
  152.     print("="*60)
  153.  
  154.     items = [
  155.         ("Laptop", 500, 2),
  156.         ("Camera", 300, 1),
  157.         ("Books", 150, 3),
  158.         ("Clothes", 200, 4),
  159.         ("Food", 100, 2),
  160.         ("Tent", 400, 5),
  161.         ("Sleeping Bag", 250, 3),
  162.         ("First Aid", 180, 1),
  163.     ]
  164.  
  165.     values = [item[1] for item in items]
  166.     weights = [item[2] for item in items]
  167.     capacity = 10  # kg
  168.  
  169.     max_val, selected = knapsack_01_dp(values, weights, capacity)
  170.  
  171.     print(f"Backpack capacity: {capacity} kg")
  172.     print(f"Maximum value: ${max_val}")
  173.     print("\nSelected items:")
  174.     total_weight = 0
  175.     for i in selected:
  176.         name, value, weight = items[i]
  177.         total_weight += weight
  178.         print(f"  - {name}: ${value} ({weight} kg)")
  179.     print(f"Total weight: {total_weight} kg")
  180.  
  181.  
  182. if __name__ == "__main__":
  183.     run_examples()
Success #stdin #stdout 0.11s 13972KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
============================================================
EXAMPLE 1: Classic 0/1 Knapsack
============================================================

==================================================
0/1 KNAPSACK SOLUTION
==================================================
Items: 3
Capacity: 50
Max Value: 220
Selected Items: [1, 2]
Total Weight: 50
Total Value: 220

Item Details:
  Item 1: value=100, weight=20
  Item 2: value=120, weight=30

Brute Force Result: 220
Brute Force Selected: [1, 2]

============================================================
EXAMPLE 2: Larger Knapsack
============================================================

==================================================
0/1 KNAPSACK SOLUTION
==================================================
Items: 6
Capacity: 10
Max Value: 60
Selected Items: [0, 3]
Total Weight: 9
Total Value: 60

Item Details:
  Item 0: value=20, weight=1
  Item 3: value=40, weight=8

============================================================
EXAMPLE 3: Backpack Problem
============================================================
Backpack capacity: 10 kg
Maximum value: $1380

Selected items:
  - Laptop: $500 (2 kg)
  - Camera: $300 (1 kg)
  - Tent: $400 (5 kg)
  - First Aid: $180 (1 kg)
Total weight: 9 kg
https://ideone.com/nIN2Vh
language:
Python 3 (python  3.12)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!