在這篇文章中，我們將瞭解貪心演算法和動態規劃方法之間的區別。貪心演算法它是一種演算法正規化，逐步構建解決方案。下一步的選擇使得其能獲得最明顯和最直接的收益。涉及選擇區域性最優值的問題將有助於選擇問題的全域性最優值/解決方案。這些是與貪心演算法相關的問題。不能保證貪心演算法會產生最優解。在問題的每個階段都會做出最優選擇，即區域性最優解。它 ... 閱讀更多

它類似於之前的演算法。這裡唯一的區別是，圖 G(V, E) 由鄰接表表示。鄰接表表示的時間複雜度為 O(E log V)。輸入和輸出輸入：成本矩陣：輸出：邊：A--B 和成本：1 邊：B--E 和成本：2 邊：A--C 和成本：3 邊：A--D 和成本：4 邊：E--F 和成本：2 邊：F--G 和成本：3 總成本：15演算法prims(g: 圖，開始)輸入 - 圖 g 和名為“開始”的種子頂點輸出 - 新增邊後的樹。開始 建立兩個集合 B、N 將起始節點新增到 B 中 ... 閱讀更多

給定一個連通圖 G(V, E)，並且給出了每條邊的權重或成本。Prim 演算法將從圖 G 中找到最小生成樹。它是一種增長樹方法。該演算法需要一個種子值來啟動樹。種子頂點會增長形成整棵樹。該問題將使用兩個集合來解決。一個集合儲存已選擇的節點，另一個集合儲存尚未考慮的項。從種子頂點開始，它根據最小邊成本獲取相鄰頂點，因此它透過 ... 閱讀更多

給定到達時間和離開時間的列表。現在問題是找到鐵路所需的最小站臺數量，因為沒有火車等待。透過對所有時間進行排序，我們可以輕鬆找到解決方案，這將很容易跟蹤火車何時到達但尚未離開車站。此問題的時間複雜度為 O(n Log n)。輸入和輸出輸入：到達時間和離開時間的列表。到達：{900, 940, 950, 1100, 1500, 1800} 離開：{910, 1200, 1120, 1130, 1900, 2000} 輸出：所需的最小站臺數量：3演算法minPlatform(到達，離開，int n)輸入 - ... 閱讀更多

給定一個硬幣列表 C(c1, c2, ……Cn) 和一個值 V。現在問題是如何使用最少的硬幣來構成價值 V。注意 - 假設有無限數量的硬幣 C在這個問題中，我們將考慮給定的一組不同的硬幣 C{1, 2, 5, 10}，每種型別的硬幣都有無限多個。為了構成請求的值，我們將嘗試取任何型別的最少數量的硬幣。例如，對於值 22 - 我們將選擇 {10, 10, 2}，... 閱讀更多

在之前的霍夫曼編碼問題中，頻率沒有排序。如果頻率列表按排序順序給出，則分配程式碼的任務將更加高效。在這個問題中，我們將使用兩個空佇列。然後為每個唯一字元建立一個葉子節點，並將其按頻率遞增的順序插入佇列中。在這種方法中，演算法的複雜度為 O(n)。輸入和輸出輸入：不同的字母及其按排序順序的頻率 字母：{L, K, X, C, E, B, A, F} 頻率：{1, 1, 2, 2, 2, 2, 3, 4} 輸出：字母的程式碼 L: ... 閱讀更多

霍夫曼編碼是一種無損資料壓縮演算法。在此演算法中，為輸入的不同字元分配可變長度的程式碼。程式碼長度與字元的使用頻率相關。最常出現的字元具有最小的程式碼，而最不常出現的字元具有較長的程式碼。主要有兩個部分。第一個是建立霍夫曼樹，另一個是遍歷樹以查詢程式碼。例如，考慮一些字串“YYYZXXYYX”，字元 Y 的頻率大於 X，字元 Z 的頻率最小。因此，Y 的程式碼長度小於 ... 閱讀更多

給定一個圖 G(V, E) 及其鄰接表表示，並且還提供了一個源頂點。Dijkstra 演算法用於查詢從源頂點到圖 G 的任何其他頂點的最小最短路徑。為了解決這個問題，我們將使用兩個列表。一個是儲存已被視為最短路徑樹的頂點，另一個將儲存尚未考慮的頂點。在演算法的每個階段，我們找到未考慮的頂點，並且該頂點與源的距離最小。另一個列表用於儲存前驅節點。使用 ... 閱讀更多

給定 n 個不同的活動及其開始時間和結束時間。選擇由一個人解決的最大數量的活動。我們將使用貪心方法來查詢下一個活動，該活動的結束時間在剩餘活動中最小，並且開始時間大於或等於最後一個選定活動的結束時間。此問題的時間複雜度為 O(n log n)，前提是列表未排序。如果提供排序列表，則複雜度將為 O(n)。輸入和輸出輸入：一個帶有開始和結束時間的不同活動的列表。{(5，... 閱讀更多