A mohó algoritmus egy optimalizálási megközelítés, amely mindig azt a lépést választja, amely az adott pillanatban a legjobb helyi megoldást nyújtja, abban a reményben, hogy ez a választás a teljes problémára is optimális megoldást eredményez.
Adott (n) tárgy, mindegyiknek van egy súlya és értéke. A cél, hogy maximalizáljuk az értéket egy (W) kapacitású hátizsákban. Az egyes tárgyak töredékekben is elhelyezhetők.
function FractionalKnapsack(weights, values, capacity):
Rendezés csökkenő (value / weight) arány szerint.
total_value = 0
minden tárgy w, v:
ha w <= capacity:
total_value += v
capacity -= w
különben:
total_value += v * (capacity / w)
térj vissza total_value
def fractional_knapsack(weights, values, capacity):
items = sorted(zip(weights, values), key=lambda x: x/x, reverse=True)
total_value = 0
for weight, value in items:
if capacity >= weight:
total_value += value
capacity -= weight
else:
total_value += value * (capacity / weight)
break
return total_value
# Példa használat
weights =
values =
capacity = 50
print(f"Maximális érték: {fractional_knapsack(weights, values, capacity)}")
Kimenet:
Maximális érték: 240.0
Adj vissza egy adott összegű pénzt a lehető legkevesebb érme használatával, adott érmecímletekkel.
function CoinChange(coins, amount):
coins.sort(descending)
result = 0
minden érme c in coins:
ha amount == 0:
térj vissza result
result += amount // c
amount %= c
ha amount > 0:
térj vissza "Nincs megoldás"
def coin_change(coins, amount):
coins = sorted(coins, reverse=True)
result = 0
for coin in coins:
if amount == 0:
break
result += amount // coin
amount %= coin
if amount > 0:
return -1 # Nincs pontos megoldás
return result
# Példa használat
coins =
amount = 63
print(f"Minimális érmék száma: {coin_change(coins, amount)}")
Kimenet:
Minimális érmék száma: 6
Adott (n) intervallum (kezdési és befejezési időpontokkal). A cél a maximális számú, egymást nem átfedő intervallum kiválasztása.
function IntervalScheduling(intervals):
Rendezés növekvő befejezési idő szerint.
selected =
last_end = -∞
minden intervallum i in intervals:
ha i kezdési idő > last_end:
add i-t a selected listához
last_end = i befejezési idő
térj vissza selected
def interval_scheduling(intervals):
intervals = sorted(intervals, key=lambda x: x) # Befejezési idő szerint rendezve
selected =
last_end = float('-inf')
for start, end in intervals:
if start >= last_end:
selected.append((start, end))
last_end = end
return selected
# Példa használat
intervals =
print(f"Kiválasztott intervallumok: {interval_scheduling(intervals)}")
Kimenet:
Kiválasztott intervallumok:
A mohó algoritmusok hatékony megoldást nyújtanak sok optimalizálási problémára, ha: - A probléma rendelkezik az optimális almotívum tulajdonságával (az optimális megoldás részmegoldásokból épül fel). - A probléma mohó tulajdonsága biztosítja, hogy a helyi döntések összeállnak egy globálisan optimális megoldássá.
Előnyök: - Gyors, egyszerű algoritmusok. - Jó közelítő megoldásokat adhat még akkor is, ha a globális optimumot nem garantálja.
Hátrányok: - Nem minden probléma oldható meg optimálisan mohó módszerekkel. - Bizonyos esetekben a helyi optimum nem vezet globális optimumhoz.