手机网站模板开发工具,用wordpress搭建商店,dw做的网站怎么让别人看到,wordpress4.9漏洞利用概念
贪心算法是一种在每一步选择中都选择当前最优解的算法策略。这种方法适用于某些特定问题#xff0c;可以通过局部最优选择构建全局最优解。
特点
局部最优选择#xff1a;每一步选择都选择当前看起来最优的解。无后效性#xff1a;当前选择不会影响未来选择的可能性…概念
贪心算法是一种在每一步选择中都选择当前最优解的算法策略。这种方法适用于某些特定问题可以通过局部最优选择构建全局最优解。
特点
局部最优选择每一步选择都选择当前看起来最优的解。无后效性当前选择不会影响未来选择的可能性。可行性必须确保每一步的选择是可行的。
优缺点
优点
简单易懂贪心算法通常比其他算法如动态规划更简单逻辑清晰易于实现和理解。高效在适合的场景下贪心算法通常具有较低的时间复杂度能在较短时间内找到解。节省空间由于贪心算法在求解过程中不需要存储大量的中间结果相对节省内存空间。适用性广对于一些特定类型的问题贪心算法能够有效地找到全局最优解。
缺点
不适用于所有问题贪心算法并不适用于所有问题有些问题不能通过局部最优解得到全局最优解。缺乏最优性保证在某些情况下贪心策略可能导致错误的结果即找到的解不是最优解。例如在 0-1 背包问题中简单的贪心算法可能无法得到最优解。难以分析对于一些复杂的问题判断贪心选择是否能导致全局最优解需要进行深入分析和证明。局部最优陷阱有时贪心选择看似合理但最终结果却不理想导致程序错误或效率低下。
应用场景 活动选择问题 最小生成树 单源最短路径 背包问题 Huffman 编码
活动选择问题
问题描述给定一组活动选择不重叠的活动以最大化活动数量。
#include iostream
#include vector
#include algorithmstruct Activity {int start;int end;
};bool compare(Activity a1, Activity a2) {return a1.end a2.end;
}void activitySelection(std::vectorActivity activities) {std::sort(activities.begin(), activities.end(), compare);std::cout 选择的活动: \n;int lastEndTime -1;for (const auto activity : activities) {if (activity.start lastEndTime) {std::cout 活动( activity.start , activity.end )\n;lastEndTime activity.end;}}
}int main() {std::vectorActivity activities {{1, 3}, {2, 5}, {4, 6}, {6, 7}, {5, 8}, {8, 9}};activitySelection(activities);return 0;
}最小生成树Kruskal 算法
问题描述给定一个带权无向图找到最小生成树。
#include iostream
#include vector
#include algorithmstruct Edge {int src, dest, weight;
};bool compare(Edge e1, Edge e2) {return e1.weight e2.weight;
}class DisjointSet {
public:DisjointSet(int n) : parent(n), rank(n, 0) {for (int i 0; i n; i) parent[i] i;}int find(int u) {if (u ! parent[u])parent[u] find(parent[u]);return parent[u];}void unionSets(int u, int v) {int rootU find(u);int rootV find(v);if (rootU ! rootV) {if (rank[rootU] rank[rootV]) {parent[rootU] rootV;} else if (rank[rootU] rank[rootV]) {parent[rootV] rootU;} else {parent[rootV] rootU;rank[rootU];}}}
private:std::vectorint parent;std::vectorint rank;
};void kruskal(int n, std::vectorEdge edges) {std::sort(edges.begin(), edges.end(), compare);DisjointSet ds(n);std::cout 最小生成树的边:\n;for (const auto edge : edges) {if (ds.find(edge.src) ! ds.find(edge.dest)) {ds.unionSets(edge.src, edge.dest);std::cout edge.src - edge.dest (权重: edge.weight )\n;}}
}int main() {int n 4; // 顶点数std::vectorEdge edges {{0, 1, 10}, {0, 2, 6}, {0, 3, 5},{1, 3, 15}, {2, 3, 4}};kruskal(n, edges);return 0;
}单源最短路径Dijkstra 算法
问题描述在带权图中找到从源节点到其他所有节点的最短路径。
#include iostream
#include vector
#include queue
#include climitstypedef std::pairint, int Pair; // (距离, 节点)void dijkstra(int src, const std::vectorstd::vectorPair graph) {int n graph.size();std::vectorint dist(n, INT_MAX);dist[src] 0;std::priority_queuePair, std::vectorPair, std::greaterPair pq;pq.push({0, src}); // (距离, 节点)while (!pq.empty()) {int u pq.top().second;pq.pop();for (const auto edge : graph[u]) {int v edge.first;int weight edge.second;if (dist[u] weight dist[v]) {dist[v] dist[u] weight;pq.push({dist[v], v});}}}std::cout 从源节点 src 到其他节点的最短路径:\n;for (int i 0; i n; i) {std::cout 到节点 i 的距离: dist[i] \n;}
}int main() {std::vectorstd::vectorPair graph {{{1, 1}, {2, 4}},{{2, 2}, {3, 6}},{{3, 3}},{}};dijkstra(0, graph);return 0;
}0-1 背包问题动态规划与贪心结合
问题描述给定一组物品每个物品有重量和价值目标是最大化背包内物品的总价值。
#include iostream
#include vector
#include algorithmstruct Item {int value;int weight;
};bool compare(Item a, Item b) {return (double)a.value / a.weight (double)b.value / b.weight;
}double fractionalKnapsack(std::vectorItem items, int capacity) {std::sort(items.begin(), items.end(), compare);double totalValue 0.0;for (const auto item : items) {if (capacity 0) break;if (item.weight capacity) {capacity - item.weight;totalValue item.value;} else {totalValue item.value * ((double)capacity / item.weight);capacity 0;}}return totalValue;
}int main() {std::vectorItem items {{60, 10}, {100, 20}, {120, 30}};int capacity 50;double maxValue fractionalKnapsack(items, capacity);std::cout 最大价值: maxValue \n;return 0;
}Huffman 编码
问题描述给定一组字符及其频率构建最优的前缀编码。
#include iostream
#include queue
#include unordered_map
#include vectorstruct Node {char ch;int freq;Node* left;Node* right;Node(char character, int frequency) : ch(character), freq(frequency), left(nullptr), right(nullptr) {}
};struct Compare {bool operator()(Node* l, Node* r) {return l-freq r-freq;}
};void printCodes(Node* root, std::string str) {if (!root) return;if (!root-left !root-right) {std::cout root-ch : str \n;}printCodes(root-left, str 0);printCodes(root-right, str 1);
}void huffmanCoding(const std::unordered_mapchar, int freqMap) {std::priority_queueNode*, std::vectorNode*, Compare minHeap;for (const auto pair : freqMap) {minHeap.push(new Node(pair.first, pair.second));}while (minHeap.size() 1) {Node* left minHeap.top(); minHeap.pop();Node* right minHeap.top(); minHeap.pop();Node* newNode new Node($, left-freq right-freq);newNode-left left;newNode-right right;minHeap.push(newNode);}Node* root minHeap.top();std::cout Huffman 编码:\n;printCodes(root, );
}int main() {std::unordered_mapchar, int freqMap {{a, 5}, {b, 9}, {c, 12}, {d, 13}, {e, 16}, {f, 45}};huffmanCoding(freqMap);return 0;
}总结
贪心算法虽然简单易懂但并不是所有问题都适用。在实现贪心算法时需要确保每一步的局部选择能够导向全局最优解。
