貪婪演演算法是什麼

貪婪演演算法是一種常見的演演算法思想，主要應用於優化問題中，特別是在電腦科學和運籌學領域中。貪婪演演算法的核心思想是每一步都選擇當前最好的選項，從而得到全域性最優解。

貪婪演演算法通常包括以下步驟：

確定問題的最優子結構：即在問題中尋找那些可以自行解決的子問題。
開始構建解決方案：從問題的初始狀態開始，按照某種規則選擇一個最優解，並將其新增到中間方案中。該步驟不斷重複，直到找到全域性最優解。
判斷可行性：為了確保得到一個全域性最優解，需要在每個構建解決方案的步驟中，檢查得到的區域性最優解是否是可行的。如果當前的區域性最優解無法滿足問題的限制條件，則需要放棄此區域性最優解，重新開始構建方案。

貪婪演演算法的優點是輸入資料越大，執行時間越短；同時，由於貪婪演演算法的設計都是區域性的最優決策，不是全域性的最優決策，因此可能不會得到最優解，但通常會得到接近最優解的解決方案。

貪婪演演算法適用於一些特殊的演演算法場景，如圖論中的最小生成樹演演算法、哈夫曼編碼等。同時，在一些工業設計、物流計劃及經濟學領域中也有應用。

貪婪演演算法需要注意的問題是不能保證一定得到全域性最優解，有可能會導致次優解的出現。因此，在具體應用中，需要充分了解問題的性質，深入分析問題才能設計出較好的貪婪演演算法。

旅行商問題

一個旅行商要拜訪n個城市，求他走的最短路徑。

解題思路：

隨意選擇一個城市作為起點
從該城市出發，依次經過還未存取的最近的城市
計算路徑長度，並記錄已存取的城市
重複步驟2-3，直到所有城市都被存取
返回起點城市，路徑長度即為最短路徑

// cities為城市數量，dist為城市間距離矩陣
function TSP (cities, dist)
    visited = [false] * cities // 初始化所有城市未被存取
    current_city = 0 // 從城市0開始
    visited[current_city] = true // 標記當前城市為已存取
    path = [current_city] // 記錄遍歷路徑
    total_distance = 0 // 路徑總距離
    while true:
        if len(path) == cities: // 若所有城市都已存取過，則返回起點城市並計算路徑總距離
            total_distance += dist[current_city][0] // 加上最後一個城市到起點城市的距離
            path.append(0)
            return path, total_distance
        next_city = -1 // 下一個要存取的城市
        min_distance = Inf // 到下一個城市路徑的最小距離
        for i in range(cities):
            if not visited[i] and dist[current_city][i] < min_distance:
                next_city = i
                min_distance = dist[current_city][i]
        current_city = next_city // 更新當前城市
        visited[current_city] = true // 標記新城市為已存取
        path.append(current_city) // 記錄經過的城市
        total_distance += min_distance // 累計最小距離

部分揹包問題

有n個物品和一個容量為C的揹包，每個物品都有自己的價值和重量，求裝入揹包的物品的最大價值。

1.計算每個物品的價效比（價值/重量）。

2.將物品按價效比從高到低排序。

3.從價效比最高的物品開始，依次放入揹包，直到揹包裝滿或所有物品都放入揹包。

function fractional_knapsack(n, item, C)
// n表示物品數量，item為物品陣列，C為揹包容量
for i from 1 to n do
item[i].ratio = item[i].value / item[i].weight
// 計算每個物品的價效比


sort item by decreasing ratio
// 將物品按價效比從高到低排序

total_value = 0
for i from 1 to n do
    if C >= item[i].weight then
        total_value += item[i].value
        C -= item[i].weight
        // 如果揹包容量可以放下物品i，則將物品i完全放入揹包
    else
        total_value += C * item[i].ratio
        break
        // 否則將物品i按比例分割，在揹包中放入一部分
        // 直到揹包裝滿或物品i全部放入

return total_value
// 返回裝入揹包的物品的最大價值

區間排程問題

給定n個區間，求用盡可能少的區間覆蓋整個區間的最大數量。

首先按照區間結束時間的順序將所有區間排序（從小到大），設排序後的區間序列為intervals。
初始化變數end為區間intervals[0]的結束時間，計數器count為1，表示第一個區間一定要選。
遍歷排序後的區間序列intervals，如果當前區間的開始時間大於等於end，則選擇該區間，將end更新為該區間的結束時間，計數器count加1。
最後輸出計數器count即為最大數量。

sort(intervals) // 對區間按照結束時間進行排序
end = intervals[0].end // 初始化end為第一個區間的結束時間
count = 1 // 初始化計數器count為1
for i in range(1, intervals.size()):
if intervals[i].start >= end:
count += 1
end = intervals[i].end
print(count) // 輸出最大數量

最小罰款問題

某市道路有n個路口需要維修，第i個路口在時間ti - li到ti + li之間維修，若在該時段經過會被罰款wi。求如何安排維修時間，使得罰款總額最小。

將每個路口按照維修起始時間遞增排序
遍歷所有路口，維護一個區間集合，表示當前需要維修的路口時間段
對於每個路口，如果它的維修時間段與當前區間集合存在交集，則將交集部分取出，並且計算該部分的罰款總額
將該路口的維修時間段加入當前區間集合，維護集合的增序，重複步驟3，直至處理完所有路口

# 將每個路口按照維修起始時間遞增排序
sorted_intervals = sorted(intervals, key=lambda x: x[0])

# 初始：空集合 s，罰款總額 total = 0
s = set()
total = 0

# 遍歷所有路口
for interval in sorted_intervals:
    # 維修時間段 [ti-li, ti+li] 表示為區間 [l,r]
    l, r, w = interval

    # 逐個處理當前區間集合中的所有區間
    remove_intervals = set()
    for i in s:
        # 計算 區間 interval 與 i 的交集
        a, b = max(l, i[0]), min(r, i[1])
        if a <= b:
            # 將交集 [a,b] 內的路口從集合 s 中刪除
            remove_intervals.add(i)
            # 將交集內的罰款總額加入 total
            total += w * (b - a + 1)

    # 從集合 s 中刪除所有交集區間
    s -= remove_intervals
    # 將區間 [l,r] 加入集合 s
    s.add((l, r))

# 對於集合 s 中所有區間，以左端點為第一關鍵字，右端點為第二關鍵字進行排序
s = sorted(s, key=lambda x: (x[0], x[1]))

# 返回罰款總額
return total

跳躍遊戲

給定一個陣列，陣列中的每個元素代表你在該位置可以跳躍的最大長度，求是否可以到達最後一個元素。

記錄一個變數max_reach表示當前所能到達的最遠距離，初始值為第一個元素的距離。
對陣列從第二個元素開始遍歷： a. 如果當前位置超出了max_reach的範圍，則說明無法到達最後一個元素，返回false。 b. 否則，將當前位置能到達的最遠距離和max_reach取最大值，更新max_reach。
遍歷結束後，如果max_reach能夠到達最後一個元素，則返回true；否則，返回false。

function canJump(nums) {
    let max_reach = nums[0];
    for (let i = 1; i < nums.length; i++) {
        if (i > max_reach) {
            return false;
        }
        max_reach = Math.max(max_reach, i + nums[i]);
    }
    return max_reach >= nums.length - 1;
}

化學物質混合問題

有n種化學物質，需要混合製成一種新的化學物質，各種化學物質有自己的份量和價格，求最小的製作成本。

首先將各種化學物質按價格從小到大排序。
然後從價格最低的化學物質開始，依次按其份量的比例將其混合到目標物質中。
如果已混入的各種化學物質份量之和等於目標物質的總份量，則製作完成；否則繼續將價格次低的化學物質混入。
直到製作完成或者所有化學物質都已混入為止。

// 輸入:
// chemicals: 化學物質陣列，包括每種物質的份量和價格
// target_amount: 目標物質的總份量
// 注：程式碼中的by_price為排序關鍵字，需要根據具體實現進行定義。


function mixedChemicals(chemicals[], target_amount):
  // 按價格從小到大排序
  sort(chemicals, by_price)

  i = 0 // 當前混入的化學物質下標
  total = 0 // 已混入的各種化學物質總份量之和
  cost = 0 // 製作成本

  // 按比例依次混入各種化學物質
  while (total < target_amount) and (i < len(chemicals)):
    // 每次混入化學物質的份量
    amount = min(target_amount - total, chemicals[i].amount)
    // 每次混入的成本
    unit_cost = chemicals[i].price / chemicals[i].amount
    // 更新總成本
    cost += amount * unit_cost
    // 更新已混入的總份量
    total += amount
    // 更新當前混入的化學物質下標
    i += 1

  // 判斷是否製作成功
  if total == target_amount:
    return cost
  else:
    return '製作失敗'

資源分配問題

給定n個資源和m個任務，每個任務需要一定量的資源，其中一些任務是必須完成的，如何分配資源使得完成必須任務的代價最小。
將所有任務按是否為必須任務分成兩組：必須完成的任務和非必須任務。
對必須完成的任務按照所需資源從大到小排序。
從資源數最大的必須任務開始，依次分配資源，直到分配完畢或無法完成必須任務。
對剩餘的非必須任務按照所需資源從大到小排序。
依次給非必須任務分配資源，直到分配完畢或無法完成任務。

//將所有任務按是否為必須任務分成兩組：必須完成的任務和非必須任務。
for each task:
if task is mandatory:
add task to mandatory_tasks
else:
add task to optional_tasks



//對必須完成的任務按照所需資源從大到小排序。
sort(mandatory_tasks, by resource needed, descending)



//從資源數最大的必須任務開始，依次分配資源，直到分配完畢或無法完成必須任務。
for each task in mandatory_tasks:
if task can be completed:
allocate resources to task
else:
break



//對剩餘的非必須任務按照所需資源從大到小排序。
sort(optional_tasks, by resource needed, descending)



//依次給非必須任務分配資源，直到分配完畢或無法完成任務。
for each task in optional_tasks:
if task can be completed:
allocate resources to task
else:
break

【技術積累】演演算法中的貪婪演演算法【一】