青少年編程與數學 02-018 C++數據結構與算法 16課題、貪心算法

青少年編程與數學 02-018 C++數據結構與算法 16課題、貪心算法

  • 一、貪心算法的基本概念
    • 定義
    • 組成部分
  • 二、貪心算法的工作原理
  • 三、貪心算法的優點
  • 四、貪心算法的缺點
  • 五、貪心算法的應用實例
    • (一)找零問題
      • 問題描述:
      • 貪心策略:
      • 示例代碼:
      • 解釋:
    • (二)活動安排問題
      • 問題描述:
      • 貪心策略:
      • 示例代碼:
      • 解釋:
    • (三)霍夫曼編碼
      • 問題描述:
      • 貪心策略:
      • 示例代碼:
      • 解釋:
    • (四)最小生成樹(Kruskal算法)
      • 問題描述:
      • 貪心策略:
      • 示例代碼:
      • 解釋:
  • 六、總結

課題摘要:
貪心算法(Greedy Algorithm)是一種在每一步選擇中都采取當前狀態下最優(即最有利)的選擇,從而希望導致結果是全局最優的算法。貪心算法并不總是能得到最優解,但它在很多問題上都能得到較好的近似解,并且通常具有較高的效率。


一、貪心算法的基本概念

定義

貪心算法在每一步選擇中都采取當前狀態下最優的選擇,從而希望導致結果是全局最優的。這種“最優”通常是根據某種局部標準來衡量的。

組成部分

  1. 貪心選擇性質:問題的整體最優解可以通過一系列局部最優的選擇來達到。這是貪心算法可行的基本要素。
  2. 最優子結構:問題的最優解包含其子問題的最優解。貪心算法通過分解問題為更小的子問題來逐步構建全局最優解。
  3. 貪心策略:一種用于選擇局部最優解的策略,通常基于某種特定的規則或標準。

二、貪心算法的工作原理

  1. 貪心選擇:在每一步選擇中,根據某種貪心策略選擇當前狀態下最優的選項。例如,在找零問題中,每次選擇面值最大的硬幣。
  2. 構建解:通過一系列的貪心選擇逐步構建解。每一步的選擇都是基于當前狀態的最優選擇,而不考慮后續步驟。
  3. 驗證:在某些情況下,需要驗證通過貪心選擇得到的解是否滿足問題的約束條件。如果滿足,則該解是全局最優解;如果不滿足,則需要重新考慮貪心策略。

三、貪心算法的優點

  1. 簡單直觀:貪心算法的邏輯通常比較簡單,容易理解和實現。
  2. 效率高:貪心算法通常具有較高的效率,因為它不需要像動態規劃那樣存儲大量的子問題解。
  3. 適用性廣:貪心算法可以應用于多種問題,尤其是在組合優化問題中。

四、貪心算法的缺點

  1. 不能保證全局最優:貪心算法只能保證在每一步選擇中是局部最優的,但不能保證最終結果是全局最優的。例如,在某些背包問題中,貪心算法可能無法找到最優解。
  2. 適用范圍有限:貪心算法只能應用于具有貪心選擇性質和最優子結構的問題。對于不滿足這些條件的問題,貪心算法可能無法得到正確的解。

五、貪心算法的應用實例

(一)找零問題

問題描述:

給定一組硬幣面值和一個金額,求用最少的硬幣數湊成該金額。

貪心策略:

每次選擇面值最大的硬幣。

示例代碼:

#include <iostream>
#include <vector>
#include <algorithm>int coin_change(const std::vector<int>& coins, int amount) {std::vector<int> sorted_coins = coins;std::sort(sorted_coins.rbegin(), sorted_coins.rend());int count = 0;for (int coin : sorted_coins) {while (amount >= coin) {amount -= coin;count++;}}return amount == 0 ? count : -1;
}

解釋:

每次選擇面值最大的硬幣,直到金額為0。

(二)活動安排問題

問題描述:

給定一組活動的開始時間和結束時間,求最多可以安排多少個不沖突的活動。

貪心策略:

每次選擇結束時間最早的活動。

示例代碼:

#include <iostream>
#include <vector>
#include <algorithm>int activity_selection(const std::vector<int>& start, const std::vector<int>& finish) {std::vector<std::pair<int, int>> activities;for (size_t i = 0; i < start.size(); ++i) {activities.emplace_back(start[i], finish[i]);}std::sort(activities.begin(), activities.end(), [](const auto& a, const auto& b) {return a.second < b.second;});int count = 0;int last_finish = 0;for (const auto& activity : activities) {if (activity.first >= last_finish) {count++;last_finish = activity.second;}}return count;
}

解釋:

每次選擇結束時間最早的活動,確保后續活動不沖突。

(三)霍夫曼編碼

問題描述:

給定一組字符及其頻率,求一種最優的編碼方式,使得編碼后的字符串長度最短。

貪心策略:

每次選擇頻率最小的兩個字符合并。

示例代碼:

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
#include <string>struct Node {char ch;int freq;Node* left;Node* right;Node(char ch, int freq) : ch(ch), freq(freq), left(nullptr), right(nullptr) {}
};struct Compare {bool operator()(Node* left, Node* right) {return left->freq > right->freq;}
};void build_codes(Node* root, const std::string& prefix, std::unordered_map<char, std::string>& codes) {if (!root) return;if (root->ch != '\0') {codes[root->ch] = prefix;}build_codes(root->left, prefix + "0", codes);build_codes(root->right, prefix + "1", codes);
}std::unordered_map<char, std::string> huffman_encoding(const std::unordered_map<char, int>& frequencies) {std::priority_queue<Node*, std::vector<Node*>, Compare> pq;for (const auto& entry : frequencies) {pq.push(new Node(entry.first, entry.second));}while (pq.size() > 1) {Node* left = pq.top(); pq.pop();Node* right = pq.top(); pq.pop();Node* merged = new Node('\0', left->freq + right->freq);merged->left = left;merged->right = right;pq.push(merged);}std::unordered_map<char, std::string> codes;build_codes(pq.top(), "", codes);return codes;
}int main() {std::unordered_map<char, int> frequencies = {{'a', 5}, {'b', 9}, {'c', 12}, {'d', 13}, {'e', 16}, {'f', 45}};auto codes = huffman_encoding(frequencies);for (const auto& entry : codes) {std::cout << entry.first << ": " << entry.second << std::endl;}return 0;
}

解釋:

通過構建霍夫曼樹,為每個字符分配最優的編碼。

(四)最小生成樹(Kruskal算法)

問題描述:

給定一個加權無向圖,求一個最小生成樹。

貪心策略:

每次選擇權重最小的邊,確保不形成環。

示例代碼:

#include <iostream>
#include <vector>
#include <algorithm>class UnionFind {
public:UnionFind(int n) : parent(n) {for (int i = 0; i < n; ++i) {parent[i] = i;}}int find(int x) {if (parent[x] != x) {parent[x] = find(parent[x]);}return parent[x];}void union_sets(int x, int y) {int rootX = find(x);int rootY = find(y);if (rootX != rootY) {parent[rootX] = rootY;}}private:std::vector<int> parent;
};std::vector<std::tuple<int, int, int>> kruskal(const std::vector<std::tuple<int, int, int>>& edges, int n) {std::vector<std::tuple<int, int, int>> mst;UnionFind uf(n);std::vector<std::tuple<int, int, int>> sorted_edges(edges.begin(), edges.end());std::sort(sorted_edges.begin(), sorted_edges.end(), [](const auto& a, const auto& b) {return std::get<2>(a) < std::get<2>(b);});for (const auto& edge : sorted_edges) {int u = std::get<0>(edge);int v = std::get<1>(edge);int weight = std::get<2>(edge);if (uf.find(u) != uf.find(v)) {uf.union_sets(u, v);mst.push_back(edge);}}return mst;
}int main() {std::vector<std::tuple<int, int, int>> edges = {{0, 1, 2}, {1, 2, 3}, {2, 3, 1}, {3, 0, 4}, {0, 2, 5}};int n = 4;auto mst = kruskal(edges, n);for (const auto& edge : mst) {std::cout << std::get<0>(edge) << " - " << std::get<1>(edge) << " : " << std::get<2>(edge) << std::endl;}return 0;
}

解釋:

通過選擇權重最小的邊,逐步構建最小生成樹。

六、總結

貪心算法是一種簡單而高效的算法設計策略,適用于具有貪心選擇性質和最優子結構的問題。它通過在每一步選擇中采取當前狀態下最優的選擇,逐步構建解。雖然貪心算法不能保證總是得到全局最優解,但在很多實際問題中都能得到較好的近似解。在使用貪心算法時,需要仔細分析問題的性質,確保貪心策略的有效性。

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/bicheng/79021.shtml
繁體地址,請注明出處:http://hk.pswp.cn/bicheng/79021.shtml
英文地址,請注明出處:http://en.pswp.cn/bicheng/79021.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

UE5 Set actor Location和 Set World Location 和 Set Relative Location 的區別

在 Unreal Engine 的藍圖里&#xff0c;SetRelativeLocation、SetWorldLocation 和 SetActorLocation 三個節點雖然都能改變物體位置&#xff0c;但作用對象和坐標空間&#xff08;Coordinate Space&#xff09;不同&#xff1a; 1. SetActorLocation 作用對象&#xff1a;整個…

VINS-FUSION:跑通手機錄制數據

文章目錄 &#x1f4da;簡介&#x1f680;手機錄制數據&#x1f680;跑通數據&#x1f527;啟動rviz&#x1f527;啟動配置&#x1f527;播放rosbag&#x1f3af;跑通結果 &#x1f4da;簡介 利用智能手機的 攝像頭IMU 采集數據&#xff0c;并在 VINS-Fusion&#xff08;視覺慣…

Spring AI在大模型領域的趨勢場景題深度解析

Spring AI在大模型領域的趨勢場景題深度解析 在互聯網大廠Java求職者的面試中&#xff0c;經常會被問到關于Spring AI在大模型領域的趨勢場景的相關問題。本文通過一個故事場景來展示這些問題的實際解決方案。 第一輪提問 面試官&#xff1a;馬架構&#xff0c;歡迎來到我們…

MySQL數據庫全面詳解:從基礎到高級應用

一、數據存儲概述 在計算機系統中&#xff0c;數據可以存儲在多種形式中&#xff1a; 變量&#xff1a;程序中最基本的數據存儲單元 元組&#xff1a;不可變的序列類型&#xff0c;常用于函數返回多個值 列表&#xff1a;有序可變集合&#xff0c;可存儲不同類型元素 字典&…

Redux和MobX有什么區別

Redux 和 MobX 都是用于 React 應用的全局狀態管理庫&#xff0c;但它們在設計理念、使用方式和適用場景等方面存在明顯的區別&#xff0c;下面為你詳細分析&#xff1a; 1. 設計理念 Redux&#xff1a;基于 Flux 架構&#xff0c;遵循單向數據流和純函數式編程的理念。狀態是…

WPF實現類似Microsoft Visual Studio2022界面效果及動態生成界面技術

WPF實現類似VS2022界面效果及動態生成界面技術 一、實現類似VS2022界面效果 1. 主窗口布局與主題 <!-- MainWindow.xaml --> <Window x:Class"VsStyleApp.MainWindow"xmlns"http://schemas.microsoft.com/winfx/2006/xaml/presentation"xmlns:x…

備份服務器,備份服務器數據有哪些方法可以實現?

服務器承載著企業核心業務數據與關鍵應用&#xff0c;數據丟失或業務中斷可能帶來災難性后果。因此&#xff0c;構建一套科學、可靠的服務器數據備份體系至關重要。當前&#xff0c;服務器數據備份方法可根據技術架構、存儲介質及恢復需求進行多維劃分。根據不同場景、預算和技…

前端基礎——5、CSS border屬性與漸變色(詳解與實戰)

前端基礎——5、CSS border屬性與漸變色詳解 CSS border屬性與漸變色&#xff08;詳解與實戰&#xff09;一、border屬性全面解析1. 基礎三屬性2. 復合寫法3. 高級特性附加.border-style詳解使用示例效果&#xff1a; CSS 漸變終極指南&#xff1a;線性漸變與徑向漸變的深度解析…

企業出海降本:如何將應用從 AWS EC2 快速無縫遷移至DigitalOcean Droplet

企業出海已經成為目前最熱門的趨勢。然而不論你是做跨境電商&#xff0c;還是短劇出海&#xff0c;或處于最熱門的AI 賽道&#xff0c;你都需要使用海外的云主機或GPU云服務。海外一線的云服務平臺盡管覆蓋區域廣泛&#xff0c;但是往往費用成本較高。所以降本始終是企業出海關…

解決Spring Boot多模塊自動配置失效問題

前言 在Spring Boot多模塊項目中&#xff0c;模塊間配置不生效是一個復雜但可解決的問題&#xff0c;尤其涉及自動配置類、依賴沖突、條件注解以及IDE配置。 一、問題背景與場景 1.1 場景描述 假設存在兩個模塊&#xff1a; 模塊A&#xff1a;提供通用配置&#xff08;如跨…

WEBSTORM前端 —— 第2章:CSS —— 第4節:盒子模型

目錄 1.畫盒子 2.Pxcook軟件 3.盒子模型——組成 4.盒子模型 ——邊框線 5.盒子模型——內外邊距 6.盒子模型——尺寸計算 7.清除默認樣式 8.盒子模型——元素溢出 9.外邊距問題 ①合并現象 ②塌陷問題 10.行內元素——內外邊距問題 11.盒子模型——圓角 12.盒子…

Kafka和flume整合

需求1&#xff1a;利用flume監控某目錄中新生成的文件&#xff0c;將監控到的變更數據發送給kafka&#xff0c;kafka將收到的數據打印到控制臺&#xff1a; 在flume/conf下添加.conf文件&#xff0c; vi flume-kafka.conf # 定義 Agent 組件 a1.sourcesr1 a1.sinksk1 a1.c…

Idea 如何配合 grep console過濾并分析文件

這里寫自定義目錄標題 [grep console插件]()右擊打開文件目錄&#xff0c;選擇 tail in console 同時可以添加自己的快捷鍵。 ![新的改變](https://i-blog.csdnimg.cn/direct/03423e27cf6c40c5abd2d53982547b61.png) 隨后會在idea的菜單欄中出現tail菜單。這里&#xff0c;接下…

怎樣學習Electron

學習 Electron 是一個很好的選擇&#xff0c;特別是如果你想構建跨平臺的桌面應用程序&#xff0c;并且已經有前端開發經驗。以下是一個循序漸進的學習指南&#xff0c;幫助你從零開始掌握 Electron。 1. 基礎知識 HTML/CSS/JavaScript 確保你對這些基礎技術有扎實的理解&am…

MySQL 大數據量分頁查詢優化指南

問題分析 當對包含50萬條記錄的edu_test表進行分頁查詢時&#xff0c;發現隨著分頁越深入&#xff0c;查詢時間越長&#xff1a; limit 0,10&#xff1a;0.05秒limit 200000,10&#xff1a;0.14秒limit 499000,10&#xff1a;0.21秒 通過EXPLAIN分析發現&#xff0c;limit o…

【仿真】Ubuntu 22.04 安裝MuJoCo 3.3.2

官方GIthub下載: https://github.com/google-deepmind/mujoco/releases 官網&#xff1a;MuJoCo — Advanced Physics Simulation 文檔&#xff1a;Overview - MuJoCo Documentation 主要參考&#xff1a;Ubuntu 22.04 安裝Mujoco 3.22 - RobotStudent的文章 - 知乎 簡…

最新字節跳動運維云原生面經分享

繼續分享最新的go面經。 今天分享的是組織內部的朋友在字節的go運維工程師崗位的云原生方向的面經&#xff0c;涉及Prometheus、Kubernetes、CI/CD、網絡代理、MySQL主從、Redis哨兵、系統調優及基礎命令行工具等知識點&#xff0c;問題我都整理在下面了 面經詳解 Prometheus …

PyQt6實例_pyqtgraph散點圖顯示工具_代碼分享

目錄 描述&#xff1a; 效果&#xff1a; 代碼&#xff1a; 返回結果對象 字符型橫坐標 通用散點圖工具 工具主界面 使用舉例 描述&#xff1a; 1 本例結合實際應用場景描述散點圖的使用。在財報分析中&#xff0c;需要將數值放在同行業中進行比較&#xff0c;從而判…

純C協程框架NtyCo

原文是由寫的&#xff0c;寫的真的很好&#xff0c;原文鏈接&#xff1a;純c協程框架NtyCo實現與原理-CSDN博客 1.為什么會有協程&#xff0c;協程解決了什么問題&#xff1f; 網絡IO優化 在CS&#xff0c;BS的開發模式下&#xff0c;服務器的吞吐量是一個受關注的參數&#x…

信息系統項目管理師——第10章 項目進度管理 筆記

10項目進度管理 1.規劃進度管理&#xff1a;項目章程、項目管理計劃&#xff08;開發方法、范圍管理計劃&#xff09;、事業環境因素、組織過程資產——專家判斷、數據分析&#xff08;備選方案分析&#xff09;、會議——進度管理計劃 2.定義活動&#xff1a;WBS進一步分解&am…