The greedy method is an algorithmic paradigm that builds up a solution piece by piece, always choosing the next piece that offers the most immediate benefit or looks best at the moment. It does not look back or reconsider choices once made.
This problem allows taking fractions of items to maximize total value in a knapsack with limited capacity.
def fractional_knapsack(values, weights, capacity):
index = list(range(len(values)))
ratio = [v / w for v, w in zip(values, weights)]
index.sort(key=lambda i: ratio[i], reverse=True)
max_value = 0
for i in index:
if weights[i] <= capacity:
capacity -= weights[i]
max_value += values[i]
else:
fraction = capacity / weights[i]
max_value += values[i] * fraction
break
return max_value
values = [60, 100, 120]
weights = [10, 20, 30]
capacity = 50
print("Max value in Knapsack =", fractional_knapsack(values, weights, capacity)) # Output: 240.0
Dijkstra’s algorithm finds the shortest path from a source node to all other nodes in a weighted graph by greedily choosing the next closest node.
import heapq
def dijkstra(graph, start):
queue = [(0, start)]
distances = {node: float('inf') for node in graph}
distances[start] = 0
while queue:
curr_distance, curr_node = heapq.heappop(queue)
if curr_distance > distances[curr_node]:
continue
for neighbor, weight in graph[curr_node].items():
distance = curr_distance + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(queue, (distance, neighbor))
return distances
graph = {
'A': {'B': 10, 'C': 5},
'B': {'C': 2, 'D': 1},
'C': {'B': 3, 'D': 9, 'E': 2},
'D': {'E': 4},
'E': {'D': 6, 'A': 7}
}
print(dijkstra(graph, 'A'))