貪心演算法是什么

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

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

1. 確定問題的最優子結構：即在問題中尋找那些可以自行解決的子問題，

2. 開始構建解決方案：從問題的初始狀態開始，按照某種規則選擇一個最優解，并將其添加到中間方案中，該步驟不斷重復，直到找到全域最優解，

3. 判斷可行性：為了確保得到一個全域最優解，需要在每個構建解決方案的步驟中，檢查得到的區域最優解是否是可行的，如果當前的區域最優解無法滿足問題的限制條件，則需要放棄此區域最優解，重新開始構建方案，

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

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

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

旅行商問題

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

解題思路：

1. 隨意選擇一個城市作為起點
2. 從該城市出發，依次經過還未訪問的最近的城市
3. 計算路徑長度，并記錄已訪問的城市
4. 重復步驟2-3，直到所有城市都被訪問
5. 回傳起點城市，路徑長度即為最短路徑

// 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 = https://www.cnblogs.com/yyyyfly1/p/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個區間，求用盡可能少的區間覆寫整個區間的最大數量，

1. 首先按照區間結束時間的順序將所有區間排序（從小到大），設排序后的區間序列為intervals，
2. 初始化變數end為區間intervals[0]的結束時間，計數器count為1，表示第一個區間一定要選，
3. 遍歷排序后的區間序列intervals，如果當前區間的開始時間大于等于end，則選擇該區間，將end更新為該區間的結束時間，計數器count加1，
4. 最后輸出計數器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，求如何安排維修時間，使得罰款總額最小，

1. 將每個路口按照維修起始時間遞增排序
2. 遍歷所有路口，維護一個區間集合，表示當前需要維修的路口時間段
3. 對于每個路口，如果它的維修時間段與當前區間集合存在交集，則將交集部分取出，并且計算該部分的罰款總額
4. 將該路口的維修時間段加入當前區間集合，維護集合的增序，重復步驟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

跳躍游戲

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

1. 記錄一個變數max_reach表示當前所能到達的最遠距離，初始值為第一個元素的距離，

2. 對陣列從第二個元素開始遍歷： a. 如果當前位置超出了max_reach的范圍，則說明無法到達最后一個元素，回傳false， b. 否則，將當前位置能到達的最遠距離和max_reach取最大值，更新max_reach，

3. 遍歷結束后，如果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種化學物質，需要混合制成一種新的化學物質，各種化學物質有自己的份量和價格，求最小的制作成本，

1. 首先將各種化學物質按價格從小到大排序，

2. 然后從價格最低的化學物質開始，依次按其份量的比例將其混合到目標物質中，

3. 如果已混入的各種化學物質份量之和等于目標物質的總份量，則制作完成；否則繼續將價格次低的化學物質混入，

4. 直到制作完成或者所有化學物質都已混入為止，

// 輸入:
// 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 '制作失敗'

資源分配問題

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

//將所有任務按是否為必須任務分成兩組：必須完成的任務和非必須任務，
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

標籤：其他

上一篇：【技識訓累】演算法中的動態規劃【一】

下一篇：返回列表