文章目錄
- 一、貪心算法的基本概念
- 貪心算法的適用場景
- 二、經典問題及其 JavaScript 實現
- 1. 零錢兌換問題
- 2. 活動選擇問題
- 3. 分配問題
- 三、貪心算法的應用
- 四、總結
貪心算法（Greedy Algorithm）是一種逐步構建解決方案的方法。在每一步選擇中，貪心算法總是選擇在當前看來最優的選擇，希望通過這些局部最優選擇最終能構建出全局最優解。貪心算法的特點是簡單高效，但它并不總能保證得到最優解。
一、貪心算法的基本概念
貪心算法的核心思想是每一步都選擇當前最優的決策，不考慮未來的影響。貪心算法的基本步驟通常包括以下幾個：
- 選擇：選擇當前最優的選項。
- 驗證：驗證當前選擇是否可行（通常包括是否滿足約束條件）。
- 構建：將當前選擇加入到最終的解決方案中。
貪心算法的適用場景
貪心算法通常適用于以下場景：
- 最小生成樹：如Kruskal和Prim算法。
- 最短路徑問題：如Dijkstra算法。
- 區間調度問題：如選擇最多的不重疊區間。
二、經典問題及其 JavaScript 實現
1. 零錢兌換問題
假設我們有幾種不同面值的硬幣，1元、2元和5元。我們希望用最少數量的硬幣來湊出某個金額。
問題描述：給定不同面值的硬幣和一個總金額，求最少數量的硬幣。
/*** 求最少數量的硬幣組合* @param {number[]} coins - 硬幣面值數組* @param {number} amount - 總金額* @returns {number} - 最少硬幣數量，如果無法湊出總金額返回 -1*/
function coinChange(coins, amount) {// 硬幣面值從大到小排序coins.sort((a, b) => b - a);let count = 0;for (let coin of coins) {// 盡量使用當前面值最大的硬幣let num = Math.floor(amount / coin);count += num;amount -= num * coin;// 如果總金額為 0，直接返回if (amount === 0) return count;}// 如果無法湊出總金額，返回 -1return -1;
}// 示例：用1元、2元和5元湊出11元的最少硬幣數量
console.log(coinChange([1, 2, 5], 11)); // 輸出 3 (5 + 5 + 1)
2. 活動選擇問題
假設我們有一組活動，每個活動有開始時間和結束時間。我們希望選擇盡可能多的活動，使得它們互不重疊。
問題描述：給定一組活動，選擇盡可能多的不重疊活動。
/*** 求最多的不重疊活動數量* @param {number[][]} activities - 活動的開始和結束時間數組* @returns {number} - 最多不重疊活動數量*/
function maxActivities(activities) {// 按照活動結束時間排序activities.sort((a, b) => a[1] - b[1]);let count = 0;let end = 0;for (let activity of activities) {if (activity[0] >= end) {// 選擇當前活動count++;end = activity[1];}}return count;
}// 示例：選擇最多的不重疊活動
console.log(maxActivities([[1, 3], [2, 4], [3, 5], [0, 6], [5, 7], [8, 9], [5, 9]]));
// 輸出 4 (選擇活動 [1, 3], [3, 5], [5, 7], [8, 9])
3. 分配問題
假設我們有一組任務和一組工人，每個工人能完成的任務數量有限。我們希望盡可能多地完成任務。
問題描述：給定任務和工人的能力，盡可能多地分配任務。
/*** 求最多分配任務數量* @param {number[]} tasks - 任務難度數組* @param {number[]} workers - 工人能力數組* @returns {number} - 最多分配任務數量*/
function maxTaskAssignment(tasks, workers) {// 任務和工人分別排序tasks.sort((a, b) => a - b);workers.sort((a, b) => a - b);let taskIndex = 0;let workerIndex = 0;let count = 0;while (taskIndex < tasks.length && workerIndex < workers.length) {if (workers[workerIndex] >= tasks[taskIndex]) {// 分配任務給當前工人count++;taskIndex++;}workerIndex++;}return count;
}// 示例：盡可能多地分配任務
console.log(maxTaskAssignment([1, 2, 3], [3, 2, 1])); // 輸出 3 (每個工人完成一個任務)
三、貪心算法的應用
貪心算法在實際開發中有廣泛的應用，常見的應用場景包括：
- 圖算法：最小生成樹、最短路徑問題。
- 活動選擇：選擇最多的不重疊活動。
- 任務分配：將任務盡可能多地分配給工人。
- 區間覆蓋：用最少數量的區間覆蓋所有點。
四、總結
貪心算法是一種通過局部最優選擇構建全局最優解的方法。雖然它不總能保證得到最優解，但在許多實際問題中表現良好。通過理解和應用貪心算法，我們可以有效地解決許多復雜的優化問題。希望通過本文的介紹，大家能夠更好地理解和應用貪心算法。
