4.1 定義貪婪演算法。
貪婪演算法 (Greedy Algorithms) 是一類 演算法，通過在每一步驟做出局部最佳的決策來構建解決方案。這些決策是基於當前狀態 並且不會在未來重新考慮。
貪婪演算法常用於解決優化問題，目的是 - 最大化或最小化特定的數值。
貪婪演算法的基本原則
- 貪婪選擇: 在每一步驟，演算法都選擇認為 最好的局部選擇，期望它能導致全局最佳解。
- 最佳子結構: 問題應具有此屬性，即局部最佳解能 組合成全局最佳解。
- 單調性: 一旦選擇了一個局部最佳步驟，後續的選擇不應 使解決方案惡化。
貪婪演算法的優勢和劣勢
優勢：
- 實現簡單: 貪婪演算法通常易於理解和實現。
- 效率: 通常比複雜的演算法（如動態規劃）運行得更快。
劣勢：
- 缺乏全局最佳性: 貪婪演算法不總是導致全局最佳解。
- 不是所有問題都適合: 只有某些問題能夠通過貪婪演算法解決。
有一整類的問題最佳解是通過貪婪演算法達成的。了解這些會對你大有裨益。
4.2 換零問題。
問題:
我們有不同面額的硬幣。需要找到最少數量的硬幣來支付指定的金額。
解法:
總是選擇不超過剩餘金額的最大面額的硬幣。
時間複雜度: O(n), 其中 n 是硬幣類型的數量。
Python範例程式碼:
def min_coins(coins, amount):
coins.sort(reverse=True)
count = 0
for coin in coins:
while amount >= coin:
amount -= coin
count += 1
return count
4.3 背包問題
問題:
我們有已知價值和重量的物品。我們希望在一個固定大小的背包中裝入盡可能多的價值。
在這個問題版本中 物品可以分割。例如，我們想買不同的穀物，可以買1000克，也可以買512克。
解法:
根據單位價值（價值/重量）排序物品，並選擇最高的單位價值直到背包裝滿。
時間複雜度: O(n log n), 其中 n 是物品的數量。
Python範例程式碼:
class Item:
def __init__(self, value, weight):
self.value = value
self.weight = weight
self.ratio = value / weight
def fractional_knapsack(items, capacity):
items.sort(key=lambda x: x.ratio, reverse=True)
total_value = 0.0
for item in items:
if capacity >= item.weight:
total_value += item.value
capacity -= item.weight
else:
total_value += item.ratio * capacity
break
return total_value
4.4 用線段覆蓋問題
問題:
在一條直線上有線段，由它們的端點 (x1, x2) 定義，還有一個目標線段。需要找到最少數量的線段來覆蓋 目標線段的所有點。
解法:
根據線段的右端排序，並選擇覆蓋當前點的最小線段。
時間複雜度: O(n log n), 其中 n 是線段的數量。
Python範例程式碼:
def min_segments(segments):
segments.sort(key=lambda x: x[1])
count = 0
end = -float('inf')
for seg in segments:
if seg[0] > end:
end = seg[1]
count += 1
return count
GO TO FULL VERSION