【技术积累】算法中的贪心算法【一】
2023/6/9 5:23:12
本文主要是介绍【技术积累】算法中的贪心算法【一】,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
贪心算法是什么
贪心算法是一种常见的算法思想,主要应用于优化问题中,特别是在计算机科学和运筹学领域中。贪心算法的核心思想是每一步都选择当前最好的选项,从而得到全局最优解。
贪心算法通常包括以下步骤:
-
确定问题的最优子结构:即在问题中寻找那些可以自行解决的子问题。
-
开始构建解决方案:从问题的初始状态开始,按照某种规则选择一个最优解,并将其添加到中间方案中。该步骤不断重复,直到找到全局最优解。
-
判断可行性:为了确保得到一个全局最优解,需要在每个构建解决方案的步骤中,检查得到的局部最优解是否是可行的。如果当前的局部最优解无法满足问题的限制条件,则需要放弃此局部最优解,重新开始构建方案。
贪心算法的优点是输入数据越大,运行时间越短;同时,由于贪心算法的设计都是局部的最优决策,不是全局的最优决策,因此可能不会得到最优解,但通常会得到接近最优解的解决方案。
贪心算法适用于一些特殊的算法场景,如图论中的最小生成树算法、哈夫曼编码等。同时,在一些工业设计、物流计划及经济学领域中也有应用。
贪心算法需要注意的问题是不能保证一定得到全局最优解,有可能会导致次优解的出现。因此,在具体应用中,需要充分了解问题的性质,深入分析问题才能设计出较好的贪心算法。
旅行商问题
一个旅行商要拜访n个城市,求他走的最短路径。
解题思路:
- 随意选择一个城市作为起点
- 从该城市出发,依次经过还未访问的最近的城市
- 计算路径长度,并记录已访问的城市
- 重复步骤2-3,直到所有城市都被访问
- 返回起点城市,路径长度即为最短路径
// cities为城市数量,dist为城市间距离矩阵 function TSP (cities, dist) visited = [false] * cities // 初始化所有城市未被访问 current_city = 0 // 从城市0开始 visited[current_city] = true // 标记当前城市为已访问 path = [current_city] // 记录遍历路径 total_distance = 0 // 路径总距离 while true: if len(path) == cities: // 若所有城市都已访问过,则返回起点城市并计算路径总距离 total_distance += dist[current_city][0] // 加上最后一个城市到起点城市的距离 path.append(0) return path, total_distance next_city = -1 // 下一个要访问的城市 min_distance = Inf // 到下一个城市路径的最小距离 for i in range(cities): if not visited[i] and dist[current_city][i] < min_distance: next_city = i min_distance = dist[current_city][i] current_city = next_city // 更新当前城市 visited[current_city] = true // 标记新城市为已访问 path.append(current_city) // 记录经过的城市 total_distance += min_distance // 累计最小距离
部分背包问题
有n个物品和一个容量为C的背包,每个物品都有自己的价值和重量,求装入背包的物品的最大价值。
1.计算每个物品的性价比(价值/重量)。
2.将物品按性价比从高到低排序。
3.从性价比最高的物品开始,依次放入背包,直到背包装满或所有物品都放入背包。
function fractional_knapsack(n, item, C) // n表示物品数量,item为物品数组,C为背包容量 for i from 1 to n do item[i].ratio = item[i].value / item[i].weight // 计算每个物品的性价比 sort item by decreasing ratio // 将物品按性价比从高到低排序 total_value = 0 for i from 1 to n do if C >= item[i].weight then total_value += item[i].value C -= item[i].weight // 如果背包容量可以放下物品i,则将物品i完全放入背包 else total_value += C * item[i].ratio break // 否则将物品i按比例分割,在背包中放入一部分 // 直到背包装满或物品i全部放入 return total_value // 返回装入背包的物品的最大价值
区间调度问题
给定n个区间,求用尽可能少的区间覆盖整个区间的最大数量。
- 首先按照区间结束时间的顺序将所有区间排序(从小到大),设排序后的区间序列为intervals。
- 初始化变量end为区间intervals[0]的结束时间,计数器count为1,表示第一个区间一定要选。
- 遍历排序后的区间序列intervals,如果当前区间的开始时间大于等于end,则选择该区间,将end更新为该区间的结束时间,计数器count加1。
- 最后输出计数器count即为最大数量。
sort(intervals) // 对区间按照结束时间进行排序 end = intervals[0].end // 初始化end为第一个区间的结束时间 count = 1 // 初始化计数器count为1 for i in range(1, intervals.size()): if intervals[i].start >= end: count += 1 end = intervals[i].end print(count) // 输出最大数量
最小罚款问题
某市道路有n个路口需要维修,第i个路口在时间ti - li到ti + li之间维修,若在该时段经过会被罚款wi。求如何安排维修时间,使得罚款总额最小。
- 将每个路口按照维修起始时间递增排序
- 遍历所有路口,维护一个区间集合,表示当前需要维修的路口时间段
- 对于每个路口,如果它的维修时间段与当前区间集合存在交集,则将交集部分取出,并且计算该部分的罚款总额
- 将该路口的维修时间段加入当前区间集合,维护集合的增序,重复步骤3,直至处理完所有路口
# 将每个路口按照维修起始时间递增排序 sorted_intervals = sorted(intervals, key=lambda x: x[0]) # 初始:空集合 s,罚款总额 total = 0 s = set() total = 0 # 遍历所有路口 for interval in sorted_intervals: # 维修时间段 [ti-li, ti+li] 表示为区间 [l,r] l, r, w = interval # 逐个处理当前区间集合中的所有区间 remove_intervals = set() for i in s: # 计算 区间 interval 与 i 的交集 a, b = max(l, i[0]), min(r, i[1]) if a <= b: # 将交集 [a,b] 内的路口从集合 s 中删除 remove_intervals.add(i) # 将交集内的罚款总额加入 total total += w * (b - a + 1) # 从集合 s 中删除所有交集区间 s -= remove_intervals # 将区间 [l,r] 加入集合 s s.add((l, r)) # 对于集合 s 中所有区间,以左端点为第一关键字,右端点为第二关键字进行排序 s = sorted(s, key=lambda x: (x[0], x[1])) # 返回罚款总额 return total
跳跃游戏
给定一个数组,数组中的每个元素代表你在该位置可以跳跃的最大长度,求是否可以到达最后一个元素。
-
记录一个变量max_reach表示当前所能到达的最远距离,初始值为第一个元素的距离。
-
对数组从第二个元素开始遍历: a. 如果当前位置超出了max_reach的范围,则说明无法到达最后一个元素,返回false。 b. 否则,将当前位置能到达的最远距离和max_reach取最大值,更新max_reach。
-
遍历结束后,如果max_reach能够到达最后一个元素,则返回true;否则,返回false。
function canJump(nums) { let max_reach = nums[0]; for (let i = 1; i < nums.length; i++) { if (i > max_reach) { return false; } max_reach = Math.max(max_reach, i + nums[i]); } return max_reach >= nums.length - 1; }
化学物质混合问题
有n种化学物质,需要混合制成一种新的化学物质,各种化学物质有自己的份量和价格,求最小的制作成本。
-
首先将各种化学物质按价格从小到大排序。
-
然后从价格最低的化学物质开始,依次按其份量的比例将其混合到目标物质中。
-
如果已混入的各种化学物质份量之和等于目标物质的总份量,则制作完成;否则继续将价格次低的化学物质混入。
-
直到制作完成或者所有化学物质都已混入为止。
// 输入: // chemicals: 化学物质数组,包括每种物质的份量和价格 // target_amount: 目标物质的总份量 // 注:代码中的by_price为排序关键字,需要根据具体实现进行定义。 function mixedChemicals(chemicals[], target_amount): // 按价格从小到大排序 sort(chemicals, by_price) i = 0 // 当前混入的化学物质下标 total = 0 // 已混入的各种化学物质总份量之和 cost = 0 // 制作成本 // 按比例依次混入各种化学物质 while (total < target_amount) and (i < len(chemicals)): // 每次混入化学物质的份量 amount = min(target_amount - total, chemicals[i].amount) // 每次混入的成本 unit_cost = chemicals[i].price / chemicals[i].amount // 更新总成本 cost += amount * unit_cost // 更新已混入的总份量 total += amount // 更新当前混入的化学物质下标 i += 1 // 判断是否制作成功 if total == target_amount: return cost else: return '制作失败'
资源分配问题
- 给定n个资源和m个任务,每个任务需要一定量的资源,其中一些任务是必须完成的,如何分配资源使得完成必须任务的代价最小。
- 将所有任务按是否为必须任务分成两组:必须完成的任务和非必须任务。
- 对必须完成的任务按照所需资源从大到小排序。
- 从资源数最大的必须任务开始,依次分配资源,直到分配完毕或无法完成必须任务。
- 对剩余的非必须任务按照所需资源从大到小排序。
- 依次给非必须任务分配资源,直到分配完毕或无法完成任务。
//将所有任务按是否为必须任务分成两组:必须完成的任务和非必须任务。 for each task: if task is mandatory: add task to mandatory_tasks else: add task to optional_tasks //对必须完成的任务按照所需资源从大到小排序。 sort(mandatory_tasks, by resource needed, descending) //从资源数最大的必须任务开始,依次分配资源,直到分配完毕或无法完成必须任务。 for each task in mandatory_tasks: if task can be completed: allocate resources to task else: break //对剩余的非必须任务按照所需资源从大到小排序。 sort(optional_tasks, by resource needed, descending) //依次给非必须任务分配资源,直到分配完毕或无法完成任务。 for each task in optional_tasks: if task can be completed: allocate resources to task else: break
这篇关于【技术积累】算法中的贪心算法【一】的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-28微服务架构中API版本控制的实践
- 2024-09-28AI给的和自己写的Python代码,都无法改变输入框的内容,替换也不行
- 2024-09-27Sentinel配置限流资料:新手入门教程
- 2024-09-27Sentinel配置限流资料详解
- 2024-09-27Sentinel限流资料:新手入门教程
- 2024-09-26Sentinel限流资料入门详解
- 2024-09-26Springboot框架资料:初学者入门教程
- 2024-09-26Springboot框架资料详解:新手入门教程
- 2024-09-26Springboot企业级开发资料:新手入门指南
- 2024-09-26SpringBoot企业级开发资料新手指南