整合營銷服務商
電腦端+手機端+微信端=數據同步管理
免費咨詢熱線：
電腦端+手機端+微信端=數據同步管理
免費咨詢熱線：
y Family Tree中文版是一款專業且免費的家譜（家庭樹）制作軟件。軟件功能強大，且操作界面直觀、漂亮。它經過精心設計，可以幫助您使用簡單直觀的界面快速創建家譜。對于剛開始調查其家庭歷史的人來說，它提供了一種簡單的方法來可視化并共享有關每個人的照片，故事和基本事實的家譜。經驗更豐富的家譜學家將全面支持引用文獻，證據以及使用GEDCOM文件格式傳輸數據的選項。所謂的家庭樹就是一種描繪家庭里各個成員的數據，以及他們之間關系的樹狀結構圖。當一個家族成長到龐大規模的時候，就可以利用家庭樹來了解血脈傳承的過程，甚至也能應用在醫學上探究家族病因。My Family Tree中文版能讓使用者在新增成員的時候，加入他的出生和死亡時間、地點；用遺傳數據描述血型、外觀特征；也能附上照片或加入一段簡述；如果要更詳盡一點的話，還能添加在一生當中所發生的各種事件，成為一個人的事跡。本站提供的下載文件內附帶了語言包，可以讓軟件支持20多種語言，包括簡體中文。使用該軟件可以保護您詳細的家族史，有需要的用戶可以下載體驗！
下載地址：http://www.32r.com/soft/88554.html
1、家庭排行榜
構建交互式 家庭圖，全面支持多點觸控平移和縮放。使用新穎的日期透視圖功能可查看歷史記錄中不同點的圖表。
2、聯通
與GEDCOM高度兼容， 支持導入和導出，并完全支持ANSEL文本編碼。
3、本土化
我的家譜已被翻譯成 20多種語言，并提供更多的拼寫檢查支持。
4、報告書
從家庭組到 個人時間表生成20多種類型的可定制Web報告。
5、數據網格
使用具有高級過濾功能的數據網格批量編輯數據 。使用拼音“聽起來像”匹配進行搜索。
6、輔助功能
完全支持 可訪問性功能，包括高DPI顯示，縮放，高對比度主題，濾色器，屏幕閱讀器，鍵盤導航和閱讀困難的字體。
7、多媒體
將文檔和照片直接掃描到您的家譜中。直接從“我的家譜”查看，標記和打印 多媒體文件。
8、證據
通過我的家譜，可以輕松記錄 您家譜中存儲的所有信息的來源和 引用。
9、列印
將樹打印為大的多頁平鋪圖表，或將其另存為圖像或pdf文件。
10、數據庫
將所有家譜信息和多媒體存儲在一個緊湊的文件中 ，以便于移植。
11、統計
分析有關出生，死亡和婚姻的家庭統計數據，并在交互式時間表中查看所有家庭事件。
12、工具類
使用關系計算器 檢查誰與誰有關， 并檢測包括祖先循環的數據差異。
13、隱私
我的家譜允許您通過加密保護和備份數據。您可以使用隱私設置來控制在報告和打印輸出中導出的信息。
14、制圖
地理編碼的地方 在你的樹，并查看其中的事件發生在互動地圖上。您還可以導出地點信息以用于高級地圖服務。
15、日期
高級日期輸入，完全支持部分日期，日期范圍和純文本日期。在25個以上的日歷之一中輸入日期，并以本地化格式顯示它們。
acFamilyTree是一款Mac平臺上的家譜制作軟件，它提供了全面的家族歷史和個人信息管理工具，可以輕松創建、維護和分享您的家譜。
使用MacFamilyTree，您可以記錄您的家庭成員和祖先的生日、婚姻、職業、住址等詳細信息，并將其呈現在清晰易懂的圖表和報告中。該軟件還支持添加照片、視頻和音頻文件，以及構建家族樹、譜系圖和時間軸等功能，幫助您更好地了解您的家族歷史和文化遺產。
此外，MacFamilyTree還具有強大的分析功能，可以自動生成統計圖表和報告，幫助您發現家族歷史中的趨勢和模式，從而更好地理解您的家庭背景和文化傳承。
總之，MacFamilyTree是一款功能強大、易于使用的家譜制作軟件，適用于任何對家族歷史感興趣的人。
MacFamilyTree有以下幾個特點：
易于使用： MacFamilyTree的用戶界面簡單直觀，易于使用。您可以快速創建、編輯和維護家族成員信息，構建家族樹、譜系圖和時間軸等功能。
強大的數據管理工具: MacFamilyTree支持添加照片、視頻和音頻文件，并可記錄詳細信息如生日、婚姻、職業、住址等。此外，它還可以生成高質量的報告，以幫助您更好地了解家族歷史。
分析功能: MacFamilyTree提供了強大的分析功能，可以自動生成各種統計圖表和報告，幫助您探索家族歷史中的趨勢和模式，從而更好地了解您的家庭背景和文化傳承。
https://www.macz.com/mac/4460.html?id=ODY0NzM0Jl8mMjcuMTg2LjEzLjIxNQ%3D%3D
安全性和隱私保護: MacFamilyTree支持密碼保護和加密，確保您的家族信息安全。此外，該軟件還支持將家族歷史數據備份到iCloud或其他云存儲服務上，以確保數據的完整性和安全性。
兼容性: MacFamilyTree支持導入和導出GEDCOM格式的文件，這使得您可以與其他家譜制作軟件進行協作，例如Ancestry.com, MyHeritage等。
總之，MacFamilyTree是一款功能強大、易于使用的家譜制作軟件，具有豐富的數據管理和分析工具，可以幫助您更好地了解您的家族歷史和文化遺產。
數組是最簡單也是最常見的數據結構。它們的特點是可以通過索引（位置）輕松訪問元素。
它們是做什么用的？
想象一下有一排劇院椅。每把椅子都分配了一個位置（從左到右），因此每個觀眾都會從他將要坐的椅子上分配一個號碼。這是一個數組。將問題擴展到整個劇院（椅子的行和列），您將擁有一個二維數組（矩陣）。
特性
鏈表是線性數據結構，就像數組一樣。鏈表和數組的主要區別在于鏈表的元素不存儲在連續的內存位置。它由節點組成——實體存儲當前元素的值和下一個元素的地址引用。這樣，元素通過指針鏈接。
它們是做什么用的？
鏈表的一個相關應用是瀏覽器的上一頁和下一頁的實現。雙鏈表是存儲用戶搜索顯示的頁面的完美數據結構。
特性
堆棧是一種抽象數據類型，它形式化了受限訪問集合的概念。該限制遵循 LIFO（后進先出）規則。因此，添加到堆棧中的最后一個元素是您從中刪除的第一個元素。
堆棧可以使用數組或鏈表來實現。
它們是做什么用的？
現實生活中最常見的例子是在食堂中將盤子疊放在一起。位于頂部的板首先被移除。放置在最底部的盤子是在堆棧中保留時間最長的盤子。
堆棧最有用的一種情況是您需要獲取給定元素的相反順序。只需將它們全部推入堆棧，然后彈出它們。
另一個有趣的應用是有效括號問題。給定一串括號，您可以使用堆棧檢查它們是否匹配。
特性
隊列是受限訪問集合中的另一種數據類型，就像前面討論的堆棧一樣。主要區別在于隊列是按照FIFO（先進先出）模型組織的：隊列中第一個插入的元素是第一個被移除的元素。隊列可以使用固定長度的數組、循環數組或鏈表來實現。
它們是做什么用的？
這種抽象數據類型 (ADT) 的最佳用途當然是模擬現實生活中的隊列。例如，在呼叫中心應用程序中，隊列用于保存等待從顧問那里獲得幫助的客戶——這些客戶應該按照他們呼叫的順序獲得幫助。
一種特殊且非常重要的隊列類型是優先級隊列。元素根據與它們關聯的“優先級”被引入隊列：具有最高優先級的元素首先被引入隊列。這個 ADT 在許多圖算法（Dijkstra 算法、BFS、Prim 算法、霍夫曼編碼 ）中是必不可少的。它是使用堆實現的。
另一種特殊類型的隊列是deque 隊列（雙關語它的發音是“deck”）。可以從隊列的兩端插入/刪除元素。
特性
Maps （dictionaries）是包含鍵集合和值集合的抽象數據類型。每個鍵都有一個與之關聯的值。
哈希表是一種特殊類型的映射。它使用散列函數生成一個散列碼，放入一個桶或槽數組：鍵被散列，結果散列指示值的存儲位置。
最常見的散列函數（在眾多散列函數中）是模常數函數。例如，如果常量是 6，則鍵 x 的值是x%6。
理想情況下，散列函數會將每個鍵分配給一個唯一的桶，但他們的大多數設計都采用了不完善的函數，這可能會導致具有相同生成值的鍵之間發生沖突。這種碰撞總是以某種方式適應的。
它們是做什么用的？
Maps 最著名的應用是語言詞典。語言中的每個詞都為其指定了定義。它是使用有序映射實現的（其鍵按字母順序排列）。
通訊錄也是一張Map。每個名字都有一個分配給它的電話號碼。
另一個有用的應用是值的標準化。假設我們要為一天中的每一分鐘（24 小時 = 1440 分鐘）分配一個從 0 到 1439 的索引。哈希函數將為h(x) = x.小時*60+x.分鐘。
特性
術語：
因為maps 是使用自平衡紅黑樹實現的（文章后面會解釋），所以所有操作都在 O(log n) 內完成；所有哈希表操作都是常量。
圖是表示一對兩個集合的非線性數據結構：G={V, E}，其中 V 是頂點（節點）的集合，而 E 是邊（箭頭）的集合。節點是由邊互連的值 - 描述兩個節點之間的依賴關系（有時與成本/距離相關聯）的線。
圖有兩種主要類型：有向圖和無向圖。在無向圖中，邊(x, y)在兩個方向上都可用：(x, y)和(y, x)。在有向圖中，邊(x, y)稱為箭頭，方向由其名稱中頂點的順序給出：箭頭(x, y)與箭頭(y, x) 不同。
它們是做什么用的？
圖是各種類型網絡的基礎：社交網絡（如 weixin、csdn、weibo），甚至是城市街道網絡。社交媒體平臺的每個用戶都是一個包含他/她的所有個人數據的結構——它代表網絡的一個節點。weixin 上的好友關系是無向圖中的邊（因為它是互惠的），而在 CSDN 或 weibo上，帳戶與其關注者/關注帳戶之間的關系是有向圖中的箭頭（非互惠）。
特性
圖論是一個廣闊的領域，但我們將重點介紹一些最知名的概念：
一棵樹是一個無向圖，在連通性方面最小（如果我們消除一條邊，圖將不再連接）和在無環方面最大（如果我們添加一條邊，圖將不再是無環的）。所以任何無環連通無向圖都是一棵樹，但為了簡單起見，我們將有根樹稱為樹。
根是一個固定節點，它確定樹中邊的方向，所以這就是一切“開始”的地方。葉子是樹的終端節點——這就是一切“結束”的地方。
一個頂點的孩子是它下面的事件頂點。一個頂點可以有多個子節點。一個頂點的父節點是它上面的事件頂點——它是唯一的。
它們是做什么用的？
我們在任何需要描繪層次結構的時候都使用樹。我們自己的家譜樹就是一個完美的例子。你最古老的祖先是樹的根。最年輕的一代代表葉子的集合。
樹也可以代表你工作的公司中的上下級關系。這樣您就可以找出誰是您的上級以及您應該管理誰。
特性
二叉樹是一種特殊類型的樹：每個頂點最多可以有兩個子節點。在嚴格二叉樹中，除了葉子之外，每個節點都有兩個孩子。具有 n 層的完整二叉樹具有所有2?-1 個可能的節點。
二叉搜索樹是一棵二叉樹，其中節點的值屬于一個完全有序的集合——任何任意選擇的節點的值都大于左子樹中的所有值，而小于右子樹中的所有值。
它們是做什么用的？
BT 的一項重要應用是邏輯表達式的表示和評估。每個表達式都可以分解為變量/常量和運算符。這種表達式書寫方法稱為逆波蘭表示法 (RPN)。這樣，它們就可以形成一個二叉樹，其中內部節點是運算符，葉子是變量/常量——它被稱為抽象語法樹（AST）。
BST 經常使用，因為它們可以快速搜索鍵屬性。AVL 樹、紅黑樹、有序集和映射是使用 BST 實現的。
特性
BST 有三種類型的 DFS 遍歷：
所有這些類型的樹都是自平衡二叉搜索樹。不同之處在于它們以對數時間平衡高度的方式。
AVL 樹在每次插入/刪除后都是自平衡的，因為節點的左子樹和右子樹的高度之間的模塊差異最大為 1。 AVL 以其發明者的名字命名：Adelson-Velsky 和 ?Landis。
在紅黑樹中，每個節點存儲一個額外的代表顏色的位，用于確保每次插入/刪除操作后的平衡。
在 Splay 樹中，最近訪問的節點可以快速再次訪問，因此任何操作的攤銷時間復雜度仍然是 O(log n)。
它們是做什么用的？
AVL 似乎是數據庫理論中最好的數據結構。
RBT（紅黑樹） 用于組織可比較的數據片段，例如文本片段或數字。在 Java 8 版本中，HashMap 是使用 RBT 實現的。計算幾何和函數式編程中的數據結構也是用 RBT 構建的。
在 Windows NT 中（在虛擬內存、網絡和文件系統代碼中），Splay 樹用于緩存、內存分配器、垃圾收集器、數據壓縮、繩索（替換用于長文本字符串的字符串）。
特性
最小堆是一棵二叉樹，其中每個節點的值都大于或等于其父節點的值：val[par[x]] <= val[x]，具有堆的 xa 節點，其中val[ x]是它的值，par[x] 是它的父級。
還有一個實現相反關系的最大堆。
二叉堆是一棵完整的二叉樹（它的所有層都被填充，除了最后一層）。
它們是做什么用的？
正如我們幾天前討論過的，優先隊列可以使用二叉堆有效地實現，因為它支持 O(log n) 時間內的 insert()、delete()、extractMax() 和 reduceKey() 操作。這樣，堆在圖算法中也是必不可少的（因為優先級隊列）。
任何時候您需要快速訪問最大/最小項目，堆都是最好的選擇。
堆也是堆排序算法的基礎。
特性
trie 是一種高效的信息檢索數據結構。也稱為前綴樹，它是一種搜索樹，允許以 O(L) 時間復雜度插入和搜索，其中 L 是鍵的長度。
如果我們將密鑰存儲在一個平衡良好的 BST 中，它將需要與 L * log n 成正比的時間，其中 n 是樹中的密鑰數量。這樣，與 BST 相比，trie 是一種更快的數據結構（使用 O(L)），但代價是 trie 存儲要求。
它們是做什么用的？
樹主要用于存儲字符串及其值。它最酷的應用程序之一是在 Google 搜索欄中鍵入自動完成和自動建議。特里是最好的選擇，因為它是最快的選擇：如果我們不使用特里，更快的搜索比節省的存儲更有價值。
通過在字典中查找單詞或在同一文本中查找該單詞的其他實例，也可以使用 trie 來完成鍵入單詞的正字法自動更正。
特性
空間復雜度實際上是一個缺點：O(ALPHABET_SIZE*L*n)。
段樹是一個完整的二叉樹，可以有效地回答查詢，同時仍然可以輕松修改其元素。
給定數組中索引 i 上的每個元素代表一個用[i, i]間隔標記的葉子。將其子節點分別標記為[x, y]或[y, z]的節點將具有[x, z]區間作為標簽。因此，給定 n 個元素（0-indexed），線段樹的根將被標記為[0, n-1]。
它們是做什么用的？
它們在可以使用分而治之（我們將要討論的第一個算法概念）解決的任務中非常有用，并且還可能需要更新其元素。這樣，在更新元素時??，包含它的任何區間也會被修改，因此復雜度是對數的。例如，n 個給定元素的總和/最大值/最小值是線段樹最常見的應用。如果元素更新正在發生，二分搜索也可以使用段樹。
特性
fenwick 樹，也稱為二叉索引樹 (BIT)，是一種也用于高效更新和查詢的數據結構。與 Segment Trees 相比，BITs 需要更少的空間并且更容易實現。
它們是做什么用的？
BIT 用于計算前綴和——第 i 個位置的元素的前綴和是從第一個位置到第 i 個元素的總和。它們使用數組表示，其中每個索引都以二進制系統表示。例如，索引 10 相當于十進制系統中的索引 2。
特性
6 = 1*22+1*21+0*2? => 1"1"0 (flip)
=> 100 = 1*22+0*21+0*2? = 4;
復制代碼我們有 n 個元素，每個元素代表一個單獨的集合。并查集 (DSU) 允許我們做兩個操作：
1.UNION — 組合任意兩個集合（或者統一兩個不同元素的集合，如果它們不是來自同一個集合）； 2.FIND — 查找元素來自的集合。
它們是做什么用的？
并查集（DSU） 在圖論中非常重要。您可以檢查兩個頂點是否來自同一個連接組件，或者甚至可以統一兩個連接組件。
讓我們以城市和城鎮為例。由于人口和經濟增長的鄰近城市正在擴張，它們可以輕松創建大都市。因此，兩個城市合并在一起，他們的居民住在同一個大都市。我們還可以通過調用 FIND 函數來檢查一個人居住在哪個城市。
特性
給定一個連通圖和無向圖，該圖的生成樹是一個子圖，它是一棵樹并將所有節點連接在一起。單個圖可以有許多不同的生成樹。加權、連通和無向圖的最小生成樹 (MST) 是權重（成本）小于或等于其他所有生成樹權重的生成樹。生成樹的權重是賦予生成樹每條邊的權重之和。
它們是做什么用的？
最小生成樹（MST ）問題是一個優化問題，一個最小成本問題。有了路線網，我們可以認為影響n個城市之間建立國道的因素之一是相鄰兩個城市之間的最小距離。
國家路線就是這樣，由道路網絡圖的 MST 表示。
特性
作為一棵樹，具有 n 個頂點的圖的 MST 具有 n-1 條邊；可以使用以下方法解決：
分而治之（DAC）本身并不是一個特定的算法，而是在深入研究其他主題之前需要了解的重要算法類別。它用于解決可以劃分為與原始問題相似但規模較小的子問題的問題。然后 DAC 遞歸地求解它們，最后合并結果以找到問題的解決方案。
它分為三個階段：
它是干什么用的？
分治算法（DAC） 的一種實際應用是使用多個處理器進行并行編程，因此子問題在不同的機器上執行。
DAC 是許多算法的基礎，例如快速排序、合并排序、二分搜索或快速乘法算法。
特性
排序算法用于根據元素上的比較運算符重新排列給定元素（來自數組或列表）。當我們提到一個排序數組時，我們通常會想到升序（比較運算符是“<”）。排序有多種類型，具有不同的時間和空間復雜度。其中一些是基于比較的，有些則不是。以下是最流行/最有效的排序方法：
冒泡排序是最簡單的排序算法之一。它基于相鄰元素之間的重復交換（如果它們的順序錯誤）。它是穩定的，它的時間復雜度是 O(n2) 并且它需要 O(1) 輔助空間。
計數排序不是基于比較的排序。它基本上是使用每個元素的頻率（一種散列），確定最小值和最大值，然后在它們之間迭代以根據其頻率放置每個元素。它在 O(n) 中完成，空間與數據范圍成正比。如果輸入范圍不明顯大于元素數量，則它是有效的。
快速排序是分而治之的一個應用。它基于選擇一個元素作為樞軸（第一個、最后一個或中間值），然后交換元素以將樞軸放置在所有小于它的元素和所有大于它的元素之間。它沒有額外的空間和 O(n*log n) 時間復雜度——基于比較的方法的最佳復雜度。
歸并排序也是一個分而治之的應用程序。它將數組分成兩半，對每一半進行排序，然后合并它們。它的時間復雜度也是 O(n*log n)，所以它也像 Quick Sort 一樣超快，但不幸的是它需要 O(n) 額外空間來同時存儲兩個子數組，最后合并它們。
基數排序使用計數排序作為子程序，因此它不是基于比較的算法。我們怎么知道CS是不夠的？假設我們必須對[1, n2] 中的元素進行排序。使用 CS，我們需要 O(n2)。我們需要一個線性算法——O(n+k)，其中元素在[1, k]范圍內。它從最不重要的一個（單位）開始，到最重要的（十、百等）對元素進行逐位排序。額外空間（來自 CS）：O(n)。
搜索算法旨在檢查數據結構中元素的存在，甚至返回它。有幾種搜索方法，但這里是最受歡迎的兩種：
該算法的方法非常簡單：您從數據結構的第一個索引開始搜索您的值。您將它們一一比較，直到您的值和當前元素相等。如果該特定值不在 DS 中，則返回 -1。
時間復雜度：O(n)
BS 是一種基于分而治之的高效搜索算法。不幸的是，它只適用于排序的數據結構。作為一種 DAC 方法，您連續將 DS 分成兩半，并將搜索中的值與中間元素的值進行比較。如果它們相等，則搜索結束。無論哪種方式，如果您的值大于/小于它，搜索應該繼續在右/左半部分。
時間復雜度：O(log n)
給定一個整數 n，打印所有小于或等于 n 的素數。
Eratosthenes 篩法是解決這個問題的最有效的算法之一，它完美地適用于小于10.000.000 的n 。
該方法使用頻率列表/映射來標記[0, n]范圍內每個數字的素數：如果 x 是素數，則ok[x]=0，否則ok[x]=1。
我們開始從列表中選擇每個素數，并用 1 標記列表中的倍數——這樣，我們選擇未標記的 (0) 數。最后，我們可以在 O(1) 中輕松回答任意數量的查詢。
經典算法在許多應用中都是必不可少的，但我們可以進行一些優化。首先，我們很容易注意到 2 是唯一的偶素數，因此我們可以單獨檢查它的倍數，然后在范圍內迭代以找到從 2 到 2 的素數。其次，很明顯，對于數字 x，我們之前在迭代 2、3 等時已經檢查了 2x、3x、4x 等。這樣，我們的乘數檢查 for 循環每次都可以從 x2 開始。最后，即使這些倍數中有一半是偶數，而且我們也在迭代奇素數，因此我們可以在倍數檢查循環中輕松地從 2x 迭代到 2x。
空間復雜度：O(n)
時間復雜度：O(n*log(log n)) 用于經典算法，O(n) 用于優化算法。
給定長度為 n 的文本和長度為 m 的模式，找出文本中所有出現的模式。
Knuth-Morris-Pratt 算法 (KMP) 是解決模式匹配問題的有效方法。
天真的解決方案基于使用“滑動窗口”，每次設置新的起始索引時，我們都會比較字符與字符，從文本的索引 0 開始到索引 nm。這樣，時間復雜度是 O(m*(n-m+1))~O(n*m)。
KMP 是對樸素解決方案的優化：它在 O(n) 中完成，并且當模式具有許多重復的子模式時效果最佳。因此，它也使用滑動窗口，但不是將所有字符與子字符串進行比較，而是不斷尋找當前子模式的最長后綴，這也是它的前綴。換句話說，每當我們在某些匹配后檢測到不匹配時，我們就已經知道下一個窗口文本中的某些字符。因此，再次匹配它們是沒有用的，因此我們重新開始匹配文本中具有該前綴后的字符的相同字符。我們怎么知道我們應該跳過多少個字符？好吧，我們應該構建一個預處理數組，告訴我們應該跳過多少個字符。
Greedy 方法多用于需要優化且局部最優解導致全局最優解的問題。
也就是說，當使用 Greedy 時，每一步的最優解都會導致整體最優解。然而，在大多數情況下，我們在一個步驟中做出的決定會影響下一步的決定列表。在這種情況下，必須用數學方法證明算法。Greedy 也會在一些數學問題上產生很好的解決方案，但不是全部（可能無法保證最佳解決方案）！
貪心算法通常有五個組成部分：
分數背包問題
給定n個物品的重量和價值，我們需要將這些物品放入容量為W的背包中，以獲得背包中的最大總價值（允許取件物品：一件物品的價值與其重量成正比）。
貪心方法的基本思想是根據它們的價值/重量比對所有項目進行排序。然后，我們可以添加盡可能多的整個項目。當我們發現一件比背包中剩余重量 (w1) 重 (w2) 的物品時，我們將對其進行分割：僅取出w2-w1以最大化我們的利潤。保證這個貪心的解決方案是正確的。
動態規劃 (DP) 是一種類似于分而治之的方法。它還將問題分解為類似的子問題，但它們實際上是重疊和相互依賴的——它們不是獨立解決的。
每個子問題的結果都可以在以后隨時使用，它是使用記憶（預先計算）構建的。DP 主要用于（時間和空間）優化，它基于尋找循環。
DP 應用包括斐波那契數列、河內塔、Roy-Floyd-Warshall、Dijkstra 等。 下面我們將討論 0-1 背包問題的 DP 解決方案。
給定n個物品的重量和價值，我們需要將這些物品放入容量為W的背包中，以獲得背包中的最大總值（不允許像貪婪解決方案中的那樣分割物品）。 0-1 屬性是由我們應該選擇整個項目或根本不選擇它的事實給出的。 我們構建了一個 DP 結構作為矩陣dp[i][cw]存儲我們通過選擇總權重為 cw 的 i 個對象可以獲得的最大利潤。很容易注意到我們應該首先用v[i]初始化dp[1][w[i] ]，其中w[i]是第 i 個對象的權重，v[i] 是它的值。 復現如下：
dp[i][cw] = max(dp[i-1][cw], dp[i-1][cw-w[i]]+v[i])
復制代碼我們稍微分析一下。
dp[i-1][cw]描述了我們沒有在背包中添加當前物品的情況。dp[i-1][cw-w[i]]+v[i]就是我們添加item的情況。話雖如此，dp[i-1][cw-w[i]]是采用 i-1 個元素的最大利潤：所以它們的重量是當前重量，沒有我們的物品重量。最后，我們將項目的值添加到它。
答案存入dp[n][W]. 通過一個簡單的觀察進行優化：在循環中，當前行僅受前一行的影響。因此，將DP結構存儲到矩陣中是不必要的，因此我們應該選擇一個空間復雜度更好的數組：O(n)。時間復雜度：O(n*W)。
給定兩個序列，找出它們中存在的最長子序列的長度。子序列是以相同的相對順序出現的序列，但不一定是連續的。例如，“bcd”、“abdg”、“c”都是“abcdefg”的子序列。
這是動態規劃的另一個應用。LCS 算法使用 DP 來解決上述問題。
實際的子問題是要分別從序列 A 中的索引 i 開始，分別從序列 B 中的索引 j 中找到最長公共子序列。
接下來，我們將構建 DP 結構lcs[ ][ ]（矩陣），其中lcs[i][j]是從 A 中的索引 i 開始，分別是 B 中的索引 j 的公共子序列的最大長度。我們將以自頂向下的方式構建它。顯然，解決方案存儲在lcs[n][m] 中，其中 n 是 A 的長度，m 是 B 的長度。
遞推關系非常簡單直觀。為簡單起見，我們將考慮兩個序列都是 1 索引的。首先，我們將初始化lcs[i][0] , 1<=i<=n和lcs[0][j] , 1<=j<=m , 0, 作為基本情況（沒有從 0 開始的子序列）。然后，我們將考慮兩種主要情況：如果A[i]等于B[j]，則lcs[i][j] = lcs[i-1][j-1]+1（比之前的 LCS 多一個相同的字符）。否則，它將是lcs[i-1][j]（如果不考慮A[i]）和lcs[i][j-1]（如果不考慮B[j]）之間的最大值）。
時間復雜度：O(n*m) 附加空間：O(n*m)
給定一個包含 n 個元素的序列 A，找到最長子序列的長度，使其所有元素按遞增順序排序。子序列是以相同的相對順序出現的序列，但不一定是連續的。例如，“bcd”、“abdg”、“c”是“abcdefg”的子序列。
LIS 是另一個可以使用動態規劃解決的經典問題。
使用數組l[ ]作為 DP 結構來尋找遞增子序列的最大長度，其中l[i]是包含A[i]的遞增子序列的最大長度，其元素來自[A[i] ], ..., A[n]] 子序列。l[i]為 1，如果A[i]之后的所有元素比它小。否則，在 A[i] 之后大于它的所有元素之間的最大值為 1+。顯然，l[n]=1，其中 n 是 A 的長度。 實現是自底向上的（從末尾開始）。
在搜索當前元素之后的所有元素之間的最大值時出現了一個優化問題。我們能做的最好的事情是二分搜索最大元素。
為了找到現在已知的最大長度的子序列，我們只需要使用一個額外的數組ind[]，它存儲每個最大值的索引。
時間復雜度：O(n*log n)
附加空間：O(n)
給定同一平面中的一組 n 個點，找到包含所有給定點（位于多邊形內部或其邊上）的最小面積凸多邊形。這種多邊形稱為凸包。凸包問題是一個經典的幾何，在現實生活中有很多應用。例如，碰撞避免：如果汽車的凸包避免碰撞，那么汽車也能避免碰撞。路徑的計算是使用汽車的凸表示完成的。形狀分析也是在凸包的幫助下完成的。這樣，圖像處理很容易通過匹配模型的凸缺陷樹來完成。
有一些算法用于尋找凸包，如 Jarvis 算法、Graham 掃描等。今天我們將討論 Graham 掃描和一些有用的優化。
格雷厄姆掃描按極角對點進行排序——由某個點和其他選定點確定的線的斜率。然后用一個棧來存儲當前時刻的凸包。當一個點 x 被壓入堆棧時，其他點會被彈出堆棧，直到 x 與最后兩個點所確定的線形成小于 180° 的角度。最后，引入堆棧的最后一個點關閉多邊形。由于排序，這種方法的時間復雜度為 O(n*log n)。但是，這種方法在計算斜率時會產生精度誤差。
一種改進的解決方案具有相同的時間復雜度，但誤差較小，按坐標（x，然后是 y）對點進行排序。然后我們考慮由最左邊和最右邊的點形成的線，并將問題分為兩個子問題。最后，我們在這條線的每一邊找到了凸包。所有給定點的凸包是兩個包的重聚。
遍歷圖的問題是指以特定順序訪問所有節點，通常沿途計算其他有用信息。
廣度優先搜索 (BFS) 算法是確定圖是否連通的最常用方法之一——或者換句話說，查找 BFS 源節點的連通分量。
BFS 還用于計算源節點和所有其他節點之間的最短距離。BFS 的另一個版本是 Lee 算法，用于計算網格中兩個單元格之間的最短路徑。
該算法首先訪問源節點，然后訪問將被推入隊列的鄰居。隊列中的第一個元素被彈出。我們將訪問它的所有鄰居，并將之前未訪問的鄰居推入隊列。重復該過程直到隊列為空。當隊列為空時，表示所有可達頂點都已訪問完畢，算法結束。
深度優先搜索 (DFS) 算法是另一種常見的遍歷方法。在檢查圖形的連通性時，它實際上是最好的選擇。
首先，我們訪問根節點并將其壓入堆棧。雖然堆棧不為空，但我們檢查頂部的節點。如果該節點有未訪問的鄰居，則選擇其中一個并將其壓入堆棧。否則，如果它的所有鄰居都被訪問過，我們就會彈出這個節點。當堆棧變空時，算法結束。
經過這樣的遍歷，就形成了一個DFS樹。DFS 樹有很多應用；最常見的一種是存儲每個節點的“開始”和“結束”時間——它進入堆棧的時刻，分別是它從堆棧中彈出的時刻。
Floyd-Warshall / Roy-Floyd 算法解決了所有對最短路徑問題：找到給定邊加權有向圖中每對頂點之間的最短距離。
FW 是一個動態規劃應用程序。DP 結構（矩陣）dist[ ][ ]用輸入圖矩陣初始化。然后我們將每個頂點視為其他兩個節點之間的中間體。最短路徑在每兩對節點之間更新，任何節點 k 作為中間頂點。如果 k 是 i 和 j 之間排序路徑中的中間值，則dist[i][j]成為dist[i][k]+dist[k][j]和dist[i][j]之間的最大值。
時間復雜度：O(n3) 空間復雜度：O(n2)
給定一個圖和圖中的一個源頂點，找出從源到給定圖中所有頂點的最短路徑。
Dijkstra 算法用于在加權圖中找到這樣的路徑，其中所有的權重都是正的。
Dijkstra 是一種貪心算法，它使用以源節點為根的最短路徑樹（SPT）。SPT 是一種自平衡二叉樹，但該算法可以使用堆（或優先級隊列）來實現。我們將討論堆解決方案，因為它的時間復雜度是 O(|E|*log |V|)。這個想法是使用圖形的鄰接列表表示。這樣，節點將使用 BFS （廣度優先搜索）在 O(|V|+|E|) 時間內遍歷。
所有頂點都用 BFS 遍歷，那些最短距離尚未最終確定的頂點被存儲到最小堆（優先隊列）中。
創建最小堆并將每個節點連同它們的距離值一起推入其中。然后，源成為距離為 0 的堆的根。其他節點將無限分配為距離。當堆不為空時，我們提取最小距離值節點 x。對于與 x 相鄰的每個頂點 y，我們檢查 y 是否在最小堆中。在這種情況下，如果距離值大于 (x, y) 的權重加上 x 的距離值，那么我們更新 y 的距離值。
正如我們之前所說，Dijkstra 僅適用于正加權圖。貝爾曼解決了這個問題。給定一個加權圖，我們可以檢查它是否包含負循環。如果沒有，那么我們還可以找到從我們的源到其他源的最小距離（可能為負權重）。
Bellman-Ford 非常適合分布式系統，盡管它的時間復雜度是 O(|V| |E|)。
我們初始化一個 dist[] 就像在 Dijkstra 中一樣。對于 *|V|-1次，對于每個(x, y)邊，如果dist[y] > dist[x] + (x, y) 的權重，那么我們用它更新dist[y]。
我們重復最后一步以可能找到負循環。這個想法是，如果沒有負循環，最后一步保證最小距離。如果有任何節點在當前步驟中的距離比上一步中的距離短，則檢測到負循環。
我們之前已經討論過什么是最小生成樹。
有兩種算法可以找到圖的 MST：Prim（適用于密集圖）和 Kruskal（適用于大多數圖）。現在我們將討論 Kruskal 算法。
Kruskal 開發了一種貪心算法來尋找 MST。它在稀有圖上很有效，因為它的時間復雜度是 O(|E|*log |V|)。
該算法的方法如下：我們按權重的遞增順序對所有邊進行排序。然后，選取最小的邊。如果它不與當前 MST 形成循環，我們將其包括在內。否則，丟棄它。重復最后一步，直到 MST 中有 |V|-1 條邊。
將邊包含到 MST 中是使用 Disjoint-Set-Union 完成的，這也在前面討論過。
有向無環圖 (DAG) 只是一個不包含循環的有向圖。
DAG 中的拓撲排序是頂點的線性排序，使得對于每個拱形(x, y)，節點 x 出現在節點 y 之前。
顯然，拓撲排序中的第一個頂點是一個入度為 0 的頂點（沒有拱形指向它）。
另一個特殊屬性是 DAG 沒有唯一的拓撲排序。
BFS （廣度優先搜索）實現遵循此例程：找到一個入度為 0 的節點并將第一個推入排序。該頂點已從圖中刪除。由于新圖也是一個 DAG，我們可以重復這個過程。
在 DFS 期間的任何時候，節點都可以屬于以下三個類別之一：
如果在 DAG 中的 DFS 期間，節點 x 具有到節點 y 的輸出邊，則 y 屬于第一類或第三類。如果 y 在堆棧上，則(x, y)將結束一個循環，這與 DAG 定義相矛盾。
這個屬性實際上告訴我們一個頂點在它的所有傳出鄰居都被彈出后從堆棧中彈出。因此，要對圖進行拓撲排序，我們需要跟蹤彈出頂點的逆序列表。
*請認真填寫需求信息，我們會在24小時內與您取得聯系。
