在這篇文章中，我們將瞭解貪心演算法和動態規劃方法的區別。貪心演算法它是一種逐步構建解決方案的演算法範例。選擇下一步時，要選擇能夠帶來最明顯和直接好處的方案。涉及選擇區域性最優值的問題將有助於選擇問題的全域性最優值/解決方案。這類問題與貪心演算法相關。貪心演算法不能保證能夠找到最優解。在問題的每個階段都做出最優選擇，即區域性最優解。它……閱讀更多

它與之前的演算法類似。唯一的區別是，圖 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(arrival, departure, 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, ... 閱讀更多