贪心算法在Python、JavaScript、Java、C++和C#中的多样化实现及其在钱币找零、分数骑士、活动选择、最小生成树与哈夫曼编码问题中的应用示例

embedded/2024/9/22 19:02:27/

贪心算法是一种在每一步选择中都采取在当前状态下最好或最优(即最有利)的选择,从而希望导致结果是全局最好或最优的算法策略。贪心算法在有最优子结构的问题中尤为有效。下面我将提供5种不同编程语言实现的贪心算法示例,包括活动选择问题、钱币找零问题等。

1. Python - 钱币找零问题

python">def coinChange(coins, amount):# 贪心策略:总是优先使用最大面额的钱币coin_count = [0] * (amount + 1)coin_count[0] = 1for coin in coins:for higher_value in range(coin, amount + 1):coin_count[higher_value] += coin_count[higher_value - coin]return coin_count[amount]# 钱币面额和目标金额
coins = [1, 2, 5]
amount = 5print(coinChange(coins, amount))  # 输出可能的钱币组合数

详解:在钱币找零问题中,贪心算法总是优先考虑最大面额的钱币,从而减少所需钱币的数量。

2. JavaScript - 分数骑士问题

javascript">function fractionKnapsack(capacity, weights, values, n) {let i = 0, j = 0;while (capacity > 0 && i < n) {if (weights[j] <= capacity) {capacity -= weights[j];j++;} else {let fraction = Math.floor(capacity / weights[j]);capacity -= fraction * weights[j];j++;}}return j;
}let capacity = 50;
let values = [60, 100, 120];
let weights = [10, 20, 30];
let n = values.length;console.log(fractionKnapsack(capacity, weights, values, n));

详解:在分数骑士问题中,贪心算法选择单位价值最高的物品,如果完全装不下,则选择能够装入的最大部分。

3. Java - 活动选择问题

import java.util.Arrays;public class ActivitySelection {public static int minActivities(int[][] activities) {Arrays.sort(activities, (a, b) -> a[0] - b[0]); // 按开始时间排序int count = 0;int end = -1;for (int[] activity : activities) {if (activity[0] > end) {// 当前活动与前一个活动不重叠count++;end = activity[1];}}return count;}public static void main(String[] args) {int[][] activities = {{1, 4}, {2, 5}, {3, 6}};System.out.println(minActivities(activities)); // 输出可以选择的最大活动数}
}

详解:在活动选择问题中,贪心算法选择结束时间最早的活动,然后继续选择与之不重叠的、开始时间最早的活动。

4. C++ - 图的最小生成树 - Kruskal算法

#include <iostream>
#include <vector>
#include <algorithm>using namespace std;int findParent(vector<int> &parent, int vertex) {if (parent[vertex] == vertex)return vertex;return parent[vertex] = findParent(parent, parent[vertex]);
}void unionSets(vector<int> &parent, vector<int> &rank, int a, int b) {int aRoot = findParent(parent, a);int bRoot = findParent(parent, b);if (aRoot != bRoot) {if (rank[aRoot] < rank[bRoot])parent[aRoot] = bRoot;else if (rank[aRoot] > rank[bRoot])parent[bRoot] = aRoot;else {parent[bRoot] = aRoot;rank[aRoot]++;}}
}int main() {vector<pair<int, int>> edges = {{0, 1, 4}, {0, 2, 8}, {1, 2, 11}, {1, 3, 7}, {2, 3, 9}};int V = 4;vector<int> parent(V, -1);vector<int> rank(V, 0);sort(edges.begin(), edges.end());for (auto &edge : edges) {int a = edge.first, b = edge.second, c = edge third;int aRoot = findParent(parent, a);int bRoot = findParent(parent, b);if (aRoot != bRoot) {unionSets(parent, rank, a, b);cout << a << " - " << b << " : " << c << endl;}}return 0;
}

详解:在Kruskal算法中,我们选择边权最小的边,但是要确保这条边不会形成环。贪心算法通过不断添加最小边直到所有顶点都被连接起来。

5. C# - 哈夫曼编码

using System;class HuffmanCoding {class Node {public char ch;public int freq;public Node left, right;public Node(char ch, int freq) {this.ch = ch;this.freq = freq;}}Node CreateNode(char ch, int freq) {return new Node(ch, freq);}Node CreateTree(Frequency[] arr, int[] freq) {int start = 0;while (arr.Length != 1) {Array.Sort(arr, (x, y) => x.freq - y.freq);Node left = arr[start++];Node right = arr[start++];Node newNode = CreateNode('\0', left.freq + right.freq);newNode.left = left;newNode.right = right;arr[start++] = newNode;}return arr[0];}void PrintCodes(Node node, string str) {if (node != null) {if (node.left == null && node.right == null) {Console.WriteLine(node.ch + " : " + str);}PrintCodes(node.left, str + "0");PrintCodes(node.right, str + "1");}}public static void Main() {HuffmanCoding huffman = new HuffmanCoding();int[] freq = {10, 20, 30, 40, 50};Frequency[] arr = new Frequency[freq.Length];for (int i = 0; i < freq.Length; i++) {arr[i] = new Frequency('A' + i, freq[i]);}Node root = huffman.CreateTree(arr, freq);huffman.PrintCodes(root, "");}
}class Frequency {public char ch;public int freq;public Frequency(char ch, int freq) {this.ch = ch;this.freq = freq;}
}

详解:哈夫曼编码是一种使用频率来构建最优二叉树的贪心算法,它为每个字符赋予一个唯一的变长编码,使得整体编码的平均长度最
小。

我是小王,希望分享的内容对您有帮助,谢谢关注和支持哦!


http://www.ppmy.cn/embedded/30291.html

相关文章

linux(ubuntu18.04.2) Qt编译 MySQL(8.0以上版本)链接库 Qt版本 5.12.12及以上 包含Mysql动态库缺失问题

整理这篇文档的意义在于&#xff1a;自己走了很多弯路&#xff0c;淋过雨所以想为别人撑伞&#xff0c;也方便回顾&#xff0c;仅供参考 一、搭建开发环境&#xff1a; 虚拟机&#xff08;ubuntu-20.04.6-desktop-amd64&#xff09;&#xff1a;Mysql数据库 8.0.36Workbench …

【Linux驱动层】iTOP-RK3568学习之路(六):定时器

一、函数定义 Linux 内核中使用 timer_list 结构体表示内核定时器&#xff1a; struct timer_list {struct hlist_node entry;unsigned long expires; /* 定时器超时时间&#xff0c;单位是节拍数 */void (*function)(struct timer_list *); /* 定时处理函数 */u32 flags;…

挑战一周完成Vue3项目Day4: 用户管理+角色管理+菜单管理+首页+暗黑模式/主题切换

一、用户管理 1.静态搭建 src/views/acl/user/index.vue <template><el-card style"height:80px;"><el-form :inline"true" class"form"><el-form-item label"用户名&#xff1a;"><el-input placehold…

如何在前端展示后端返回的pdf Base64格式字符串

文章目录 如何在前端展示后端返回的pdf Base64格式字符串 如何在前端展示后端返回的pdf Base64格式字符串 // fileBase64 就是后端返回的 pdf Base64格式字符串getPdfDocument(fileBase64) {let fileBlob this.base64ToBlobsdf(fileBase64,application/pdf);let basePdfUrl …

【Python】深入理解Pandas中的连续变量与分类变量以提升模型训练效果

你啊你&#xff0c;是自在如风的少年 飞在天地间&#xff0c;比梦还遥远 你啊你&#xff0c;飞过了流转的时间 归来的时候&#xff0c;是否还有青春的容颜 &#x1f3b5; 好妹妹《你飞到城市另一边》 引言&#xff1a; 在使用Python进行数据科学和机器学…

【C++ | 运算符】介绍运算符的分类、求值顺序、优先级、结合律

&#x1f601;博客主页&#x1f601;&#xff1a;&#x1f680;https://blog.csdn.net/wkd_007&#x1f680; &#x1f911;博客内容&#x1f911;&#xff1a;&#x1f36d;嵌入式开发、Linux、C语言、C、数据结构、音视频&#x1f36d; ⏰发布时间⏰&#xff1a;2024-05-02 1…

数据库|TiDB-Server API的高效应用指南

一、API介绍 1.Status 显示TiDB 连接数、版本和git_hash 信息 tidb-server_ip:status_port/status { "connections": 0, "version": "5.7.25-TiDB-v6.1.1", "git_hash": "5263a0abda61f102122735049fd0dfadc7b7f822" } 2.St…

使用通义千问,为汽车软件需求生成测试用例

前几篇文章我们介绍了,分析需求,生成代码,生成流程图,序列图等汽车软件开发设计中的常见工作步骤,今天我们讲下汽车软件测试中怎么使用大模型,如何用千问生成用例,具体操作步骤如下: 提示词: 车速自动闭锁 使能条件(a&b&c&d&e&f) a. 电源状态…