1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118

"""
Comparison: Backtracking vs Greedy approaches to subset selection.
 
Problem: Select maximum weight subset with total ≤ capacity.
"""
 
from typing import Optional
 
# Approach 1: BACKTRACKING
# Explores all possibilities, backtracks from dead ends
 
def backtracking_subset(
    weights: list[int], 
    capacity: int
) -> tuple[int, list[int]]:
    """
    Find maximum weight subset with total ≤ capacity.
    Uses backtracking to explore all 2^n subsets.
    
    Time: O(2^n) - exponential
    Space: O(n) - recursion stack
    """
    best_weight = 0
    best_subset: list[int] = []
    
    def backtrack(index: int, current_weight: int, current_subset: list[int]):
        nonlocal best_weight, best_subset
        
        # Update best if current is better
        if current_weight > best_weight:
            best_weight = current_weight
            best_subset = current_subset.copy()
        
        # Try including remaining elements
        for i in range(index, len(weights)):
            if current_weight + weights[i] <= capacity:
                # CHOICE: Include this element
                current_subset.append(i)
                current_weight += weights[i]
                
                # EXPLORE: Recurse
                backtrack(i + 1, current_weight, current_subset)
                
                # UNCHOOSE: Backtrack - undo the decision
                current_subset.pop()
                current_weight -= weights[i]
    
    backtrack(0, 0, [])
    return best_weight, best_subset
 
 
# Approach 2: GREEDY
# Makes immediate choices, never reconsiders
 
def greedy_subset(
    weights: list[int], 
    capacity: int
) -> tuple[int, list[int]]:
    """
    Greedy approach: take largest weights that fit.
    
    Time: O(n log n) - dominated by sort
    Space: O(n) - for sorted indices
    
    NOTE: This is NOT optimal for this problem!
    But it demonstrates the greedy structure.
    """
    # Sort indices by weight (descending)
    sorted_indices = sorted(range(len(weights)), 
                           key=lambda i: weights[i], 
                           reverse=True)
    
    total_weight = 0
    selected = []
    
    for i in sorted_indices:
        if total_weight + weights[i] <= capacity:
            # COMMIT: Include this element PERMANENTLY
            selected.append(i)
            total_weight += weights[i]
            # NO BACKTRACKING: This decision is final
    
    return total_weight, selected
 
 
# Comparison
weights = [8, 4, 5, 2, 3]
capacity = 10
 
print("Weights:", weights)
print("Capacity:", capacity)
print()
 
bt_weight, bt_subset = backtracking_subset(weights, capacity)
print(f"Backtracking: weight={bt_weight}, indices={bt_subset}")
print(f"  Items: {[weights[i] for i in bt_subset]}")
 
gr_weight, gr_subset = greedy_subset(weights, capacity)
print(f"Greedy: weight={gr_weight}, indices={gr_subset}")
print(f"  Items: {[weights[i] for i in gr_subset]}")
 
# Backtracking finds optimal: 4+5=9 or 8+2=10 or 4+3+2=9...
# Actually optimal: 8+2=10 or 5+3+2=10
# Greedy: 8 first, then 2 = 10 (happens to be optimal here)
 
# Counterexample where greedy fails:
weights2 = [6, 5, 5]
capacity2 = 10
print()
print("Counterexample:")
print("Weights:", weights2, "Capacity:", capacity2)
bt_weight2, bt_subset2 = backtracking_subset(weights2, capacity2)
gr_weight2, gr_subset2 = greedy_subset(weights2, capacity2)
print(f"Backtracking: {bt_weight2} using {[weights2[i] for i in bt_subset2]}")
print(f"Greedy: {gr_weight2} using {[weights2[i] for i in gr_subset2]}")
# Backtracking: 5+5=10
# Greedy: 6 first, can't fit any 5, total=6
# Greedy FAILS because it can't undo taking 6

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108

"""
Illustration: When myopia succeeds vs when it fails.
 
We compare greedy's myopic decision to omniscient hindsight.
"""
 
from dataclasses import dataclass
 
@dataclass
class Activity:
    name: str
    start: int
    end: int
 
 
def greedy_activity_selection(activities: list[Activity]) -> list[Activity]:
    """
    Myopic selection: always take the activity that ends earliest.
    
    At each step, we see only:
    - Current time (last activity's end time)
    - Remaining candidates that start after current time
    - Their end times
    
    We do NOT consider:
    - What activities might be blocked
    - Whether alternative choices lead to more selections
    - Any future consequences
    """
    sorted_activities = sorted(activities, key=lambda a: a.end)
    selected = []
    current_time = float('-inf')
    
    for activity in sorted_activities:
        if activity.start >= current_time:
            # MYOPIC DECISION: This activity ends earliest among feasible.
            # We take it without considering alternatives.
            selected.append(activity)
            current_time = activity.end
            
    return selected
 
 
def omniscient_hindsight(activities: list[Activity]) -> int:
    """
    Omniscient view: knows all activities, computes optimal count.
    (Uses DP / exact algorithm)
    """
    if not activities:
        return 0
    
    sorted_activities = sorted(activities, key=lambda a: a.end)
    n = len(sorted_activities)
    
    # dp[i] = max activities in sorted_activities[0..i] ending with [i]
    # For activity selection, greedy IS optimal, so this matches.
    # But the computation style is "omniscient" - considers all options.
    
    # Actually, for interval scheduling, even DP reduces to greedy.
    # Let's show the contrast differently:
    
    # Optimal subset via exhaustive (exponential but shows full info)
    best_count = 0
    
    def explore(index: int, last_end: float, count: int):
        nonlocal best_count
        if index == n:
            best_count = max(best_count, count)
            return
        
        # Option 1: Skip this activity
        explore(index + 1, last_end, count)
        
        # Option 2: Take this activity (if feasible)
        if sorted_activities[index].start >= last_end:
            explore(index + 1, sorted_activities[index].end, count + 1)
    
    explore(0, float('-inf'), 0)
    return best_count
 
 
# Example where myopia succeeds
activities = [
    Activity("A", 1, 3),
    Activity("B", 2, 5),
    Activity("C", 4, 7),
    Activity("D", 6, 9),
    Activity("E", 8, 10),
]
 
greedy_result = greedy_activity_selection(activities)
optimal_count = omniscient_hindsight(activities)
 
print("Activity Selection (greedy WORKS):")
print(f"Activities: {[(a.name, a.start, a.end) for a in activities]}")
print(f"Greedy selected: {[a.name for a in greedy_result]} (count={len(greedy_result)})")
print(f"Optimal count: {optimal_count}")
print(f"Match: {len(greedy_result) == optimal_count}")
print()
 
# Illustration: WHY myopia works here
print("Why myopia succeeds for activity selection:")
print("- Taking earliest-ending A at t=1-3")
print("- This NEVER blocks a better choice, because:")
print("  Any activity starting after 3 is still available")
print("  Any activity blocked by taking A would have ended LATER")
print("  We can always 'swap' a later-ending choice for A")
print("- This is the greedy choice property in action!")

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98

"""
Demonstration: Greedy nearest-neighbor for TSP can be arbitrarily bad.
 
We construct an adversarial example where greedy produces a tour
much longer than optimal.
"""
 
import math
from itertools import permutations
 
def distance(p1: tuple[float, float], p2: tuple[float, float]) -> float:
    return math.sqrt((p1[0] - p2[0])**2 + (p1[1] - p2[1])**2)
 
 
def nearest_neighbor_tsp(cities: list[tuple[float, float]]) -> tuple[float, list[int]]:
    """
    Greedy nearest neighbor TSP.
    
    At each step:
    - Look at unvisited cities
    - Go to the closest one
    - No consideration of future consequences
    """
    n = len(cities)
    visited = [False] * n
    tour = [0]  # Start at city 0
    visited[0] = True
    total_distance = 0.0
    
    for _ in range(n - 1):
        current = tour[-1]
        nearest = -1
        nearest_dist = float('inf')
        
        for j in range(n):
            if not visited[j]:
                d = distance(cities[current], cities[j])
                if d < nearest_dist:
                    nearest_dist = d
                    nearest = j
        
        tour.append(nearest)
        visited[nearest] = True
        total_distance += nearest_dist
    
    # Return to start
    total_distance += distance(cities[tour[-1]], cities[0])
    tour.append(0)
    
    return total_distance, tour
 
 
def optimal_tsp(cities: list[tuple[float, float]]) -> float:
    """Brute force optimal TSP (exponential, for small n only)."""
    n = len(cities)
    if n <= 1:
        return 0.0
    
    best_distance = float('inf')
    
    # Try all permutations of cities 1..n-1 (city 0 is start)
    for perm in permutations(range(1, n)):
        tour = [0] + list(perm) + [0]
        dist = sum(distance(cities[tour[i]], cities[tour[i+1]]) 
                   for i in range(n))
        best_distance = min(best_distance, dist)
    
    return best_distance
 
 
# Adversarial example: cities in a "trap" configuration
# Greedy gets lured away from the efficient path
 
cities = [
    (0, 0),    # Start
    (1, 0),    # Close to start - greedy takes this first
    (2, 0),    # Next closest - greedy continues
    (3, 0),    # Greedy keeps going...
    (10, 0),   # Far away - but greedy committed to this direction
    (1.5, 3),  # Should be visited early for efficient tour!
]
 
greedy_dist, greedy_tour = nearest_neighbor_tsp(cities)
optimal_dist = optimal_tsp(cities)
 
print("Adversarial TSP Example:")
print(f"Cities: {cities}")
print()
print(f"Greedy tour: {greedy_tour}")
print(f"Greedy distance: {greedy_dist:.2f}")
print()
print(f"Optimal distance: {optimal_dist:.2f}")
print(f"Greedy is {greedy_dist/optimal_dist:.1%} of optimal")
print(f"Excess: {100*(greedy_dist/optimal_dist - 1):.1f}%")
 
# The issue: Greedy goes 0→1→2→3→4 (rightward), then must
# travel all the way back left to visit (1.5, 3), then back to 0.
# Optimal would weave efficiently to minimize backtracking.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

"""
The Ski Rental Problem: A canonical online problem.
 
You're taking a ski trip of unknown length.
- Renting skis costs $1 per day
- Buying skis costs $B (one-time)
 
You don't know how many days you'll ski.
Decision: Each day, rent or buy?
"""
 
def offline_optimal(num_days: int, buy_cost: int) -> int:
    """Optimal cost IF you knew num_days in advance."""
    rent_total = num_days * 1
    return min(rent_total, buy_cost)
 
 
def greedy_ski_rental(num_days: int, buy_cost: int) -> tuple[int, str]:
    """
    Greedy strategy: Rent until cumulative rent equals buy cost.
    Then buy.
    
    This is provably 2-competitive!
    """
    total_cost = 0
    bought = False
    actions = []
    
    for day in range(1, num_days + 1):
        if bought:
            actions.append(f"Day {day}: Using owned skis (free)")
            # No additional cost
        elif total_cost >= buy_cost - 1:
            # Next rent would exceed buy cost, so buy now
            total_cost += buy_cost
            bought = True
            actions.append(f"Day {day}: BUY for ${buy_cost} (cumulative: ${total_cost})")
        else:
            total_cost += 1
            actions.append(f"Day {day}: Rent for $1 (cumulative: ${total_cost})")
    
    return total_cost, actions
 
 
# Example
buy_cost = 10
 
print("Ski Rental Problem (Buy cost = $10)")
print("=" * 50)
 
for num_days in [3, 7, 10, 15, 20]:
    greedy_cost, actions = greedy_ski_rental(num_days, buy_cost)
    optimal = offline_optimal(num_days, buy_cost)
    ratio = greedy_cost / optimal if optimal > 0 else 1
    
    print(f"\n{num_days} days:")
    print(f"  Greedy cost: ${greedy_cost}")
    print(f"  Optimal (hindsight): ${optimal}")
    print(f"  Competitive ratio: {ratio:.2f}")
 
print("\n" + "=" * 50)
print("Greedy is at most 2-competitive (2x optimal).")
print("This is PROVABLY the best any online algorithm can do")
print("without knowing the future!")

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91

"""
Greedy with 2-opt local search for TSP.
 
1. Build initial tour greedily (nearest neighbor)
2. Improve with 2-opt swaps (limited backtracking)
"""
 
import math
 
def distance(cities, i, j):
    return math.sqrt((cities[i][0] - cities[j][0])**2 + 
                     (cities[i][1] - cities[j][1])**2)
 
 
def tour_length(cities, tour):
    return sum(distance(cities, tour[i], tour[i+1]) for i in range(len(tour)-1))
 
 
def greedy_nearest_neighbor(cities):
    """Pure greedy: nearest neighbor construction."""
    n = len(cities)
    visited = [False] * n
    tour = [0]
    visited[0] = True
    
    for _ in range(n - 1):
        current = tour[-1]
        nearest = min((j for j in range(n) if not visited[j]),
                      key=lambda j: distance(cities, current, j))
        tour.append(nearest)
        visited[nearest] = True
    
    tour.append(0)  # Return to start
    return tour
 
 
def two_opt_improvement(cities, tour):
    """
    2-opt local search: LIMITED backtracking.
    
    We don't undo the entire greedy solution—just try
    local edge swaps that might improve the tour.
    """
    n = len(tour) - 1  # tour[0] == tour[n] (start = end)
    improved = True
    
    while improved:
        improved = False
        
        for i in range(1, n - 1):
            for j in range(i + 1, n):
                # Consider reversing tour[i:j+1]
                # This effectively swaps edges (i-1,i) and (j,j+1)
                # for edges (i-1,j) and (i,j+1)
                
                old_dist = (distance(cities, tour[i-1], tour[i]) +
                           distance(cities, tour[j], tour[j+1]))
                new_dist = (distance(cities, tour[i-1], tour[j]) +
                           distance(cities, tour[i], tour[j+1]))
                
                if new_dist < old_dist - 1e-10:
                    # Improvement found! Apply the reversal.
                    tour[i:j+1] = reversed(tour[i:j+1])
                    improved = True
    
    return tour
 
 
def greedy_with_local_search(cities):
    """Hybrid: greedy construction + local search refinement."""
    tour = greedy_nearest_neighbor(cities)
    tour = two_opt_improvement(cities, tour)
    return tour
 
 
# Example
cities = [
    (0, 0), (1, 0), (2, 0), (3, 0),
    (0, 1), (1, 1), (2, 1), (3, 1),
    (0, 2), (1, 2), (2, 2), (3, 2),
]
 
greedy_tour = greedy_nearest_neighbor(cities)
hybrid_tour = greedy_with_local_search(cities)
 
print("TSP: Greedy vs Greedy + Local Search")
print(f"Cities: 4x3 grid")
print()
print(f"Pure Greedy tour length: {tour_length(cities, greedy_tour):.2f}")
print(f"Greedy + 2-opt length: {tour_length(cities, hybrid_tour):.2f}")
print(f"Improvement: {100*(1 - tour_length(cities, hybrid_tour)/tour_length(cities, greedy_tour)):.1f}%")