Spaces:
Sleeping
Sleeping
File size: 5,349 Bytes
4a3f117 | 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 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 | GREEDY ALGORITHMS
=================
Greedy algorithms make the locally optimal choice at each step hoping to find a global optimum.
They do NOT reconsider past choices (unlike DP).
When to use greedy: when local optimum leads to global optimum (greedy choice property + optimal substructure).
--- Activity Selection Problem ---
Select maximum number of non-overlapping activities.
Sort by end time, always pick activity that ends earliest.
Time: O(n log n).
def activity_selection(activities):
# activities: [(start, end), ...]
activities.sort(key=lambda x: x[1]) # sort by end time
selected = [activities[0]]
last_end = activities[0][1]
for start, end in activities[1:]:
if start >= last_end:
selected.append((start, end))
last_end = end
return selected
acts = [(1,4),(3,5),(0,6),(5,7),(3,9),(5,9),(6,10),(8,11),(8,12),(2,14),(12,16)]
print(activity_selection(acts))
# [(1,4),(5,7),(8,11),(12,16)] — 4 activities
--- Fractional Knapsack ---
Take fractions of items to maximize value. Unlike 0/1 knapsack, items can be split.
Sort by value/weight ratio. Greedy works here (not for 0/1).
Time: O(n log n).
def fractional_knapsack(weights, values, capacity):
items = sorted(zip(values, weights), key=lambda x: x[0]/x[1], reverse=True)
total_value = 0
for value, weight in items:
if capacity >= weight:
total_value += value
capacity -= weight
else:
total_value += value * (capacity / weight)
break
return round(total_value, 2)
weights = [10, 20, 30]
values = [60, 100, 120]
print(fractional_knapsack(weights, values, 50)) # Output: 240.0
--- Coin Change (Greedy — only works for canonical coin systems) ---
For standard denominations (1,5,10,25 cents), greedy gives minimum coins.
Note: greedy FAILS for arbitrary denominations — use DP instead.
def coin_change_greedy(coins, amount):
coins.sort(reverse=True)
count = 0
result = []
for coin in coins:
while amount >= coin:
amount -= coin
count += 1
result.append(coin)
return count, result
print(coin_change_greedy([1, 5, 10, 25], 41))
# Output: (4, [25, 10, 5, 1])
--- Job Scheduling to Maximize Profit ---
Schedule jobs with deadlines to maximize total profit. Each job takes 1 unit of time.
Time: O(n^2).
def job_scheduling(jobs):
# jobs: [(id, deadline, profit), ...]
jobs.sort(key=lambda x: x[2], reverse=True) # sort by profit
max_deadline = max(j[1] for j in jobs)
slots = [None] * (max_deadline + 1)
total_profit = 0
for job_id, deadline, profit in jobs:
for t in range(min(deadline, max_deadline), 0, -1):
if slots[t] is None:
slots[t] = job_id
total_profit += profit
break
scheduled = [s for s in slots if s]
return scheduled, total_profit
jobs = [('a',2,100),('b',1,19),('c',2,27),('d',1,25),('e',3,15)]
print(job_scheduling(jobs)) # (['c', 'a', 'e'], 142)
--- Huffman Encoding ---
Build optimal prefix-free codes for data compression.
Characters with higher frequency get shorter codes.
Time: O(n log n).
import heapq
def huffman_encoding(freq):
heap = [[f, [ch, ""]] for ch, f in freq.items()]
heapq.heapify(heap)
while len(heap) > 1:
lo = heapq.heappop(heap)
hi = heapq.heappop(heap)
for pair in lo[1:]:
pair[1] = '0' + pair[1]
for pair in hi[1:]:
pair[1] = '1' + pair[1]
heapq.heappush(heap, [lo[0] + hi[0]] + lo[1:] + hi[1:])
return sorted(heap[0][1:], key=lambda x: len(x[1]))
freq = {'a': 5, 'b': 9, 'c': 12, 'd': 13, 'e': 16, 'f': 45}
codes = huffman_encoding(freq)
for char, code in codes:
print(f"{char}: {code}")
# f: 0
# c: 100
# d: 101
# a: 1100
# b: 1101
# e: 111
--- Minimum Platforms (Greedy) ---
Find minimum number of platforms needed at a railway station.
Time: O(n log n).
def min_platforms(arrivals, departures):
arrivals.sort()
departures.sort()
platforms = 1
max_platforms = 1
i = 1
j = 0
while i < len(arrivals) and j < len(departures):
if arrivals[i] <= departures[j]:
platforms += 1
i += 1
else:
platforms -= 1
j += 1
max_platforms = max(max_platforms, platforms)
return max_platforms
arr = [900, 940, 950, 1100, 1500, 1800]
dep = [910, 1200, 1120, 1130, 1900, 2000]
print(min_platforms(arr, dep)) # Output: 3
--- Gas Station (Circular Route) ---
Find starting gas station to complete a circular route. Greedy: if total gas >= total cost, solution exists.
Time: O(n). Space: O(1).
def can_complete_circuit(gas, cost):
total_tank = 0
curr_tank = 0
start = 0
for i in range(len(gas)):
diff = gas[i] - cost[i]
total_tank += diff
curr_tank += diff
if curr_tank < 0:
start = i + 1
curr_tank = 0
return start if total_tank >= 0 else -1
gas = [1, 2, 3, 4, 5]
cost = [3, 4, 5, 1, 2]
print(can_complete_circuit(gas, cost)) # Output: 3
--- Greedy vs Dynamic Programming ---
Greedy: fast O(n log n), works when greedy choice is provably optimal.
DP: slower O(n^2) or O(n*W), works for all optimization problems.
Example: Fractional Knapsack → Greedy. 0/1 Knapsack → DP.
|