贪心算法是什么

贪心算法是一种常见的算法思想，主要应用于优化问题中，特别是在计算机科学和运筹学领域中。贪心算法的核心思想是每一步都选择当前最好的选项，从而得到全局最优解。

(资料图片)

贪心算法通常包括以下步骤：

确定问题的最优子结构：即在问题中寻找那些可以自行解决的子问题。

开始构建解决方案：从问题的初始状态开始，按照某种规则选择一个最优解，并将其添加到中间方案中。该步骤不断重复，直到找到全局最优解。

判断可行性：为了确保得到一个全局最优解，需要在每个构建解决方案的步骤中，检查得到的局部最优解是否是可行的。如果当前的局部最优解无法满足问题的限制条件，则需要放弃此局部最优解，重新开始构建方案。

贪心算法的优点是输入数据越大，运行时间越短；同时，由于贪心算法的设计都是局部的最优决策，不是全局的最优决策，因此可能不会得到最优解，但通常会得到接近最优解的解决方案。

贪心算法适用于一些特殊的算法场景，如图论中的最小生成树算法、哈夫曼编码等。同时，在一些工业设计、物流计划及经济学领域中也有应用。

贪心算法需要注意的问题是不能保证一定得到全局最优解，有可能会导致次优解的出现。因此，在具体应用中，需要充分了解问题的性质，深入分析问题才能设计出较好的贪心算法。

旅行商问题

一个旅行商要拜访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 doitem[i].ratio = item[i].value / item[i].weight// 计算每个物品的性价比sort item by decreasing ratio// 将物品按性价比从高到低排序total_value = 0for 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为1for i in range(1, intervals.size()):if intervals[i].start >= end:count += 1end = intervals[i].endprint(count) // 输出最大数量

最小罚款问题

某市道路有n个路口需要维修，第i个路口在时间ti - li到ti + li之间维修，若在该时段经过会被罚款wi。求如何安排维修时间，使得罚款总额最小。

将每个路口按照维修起始时间递增排序遍历所有路口，维护一个区间集合，表示当前需要维修的路口时间段对于每个路口，如果它的维修时间段与当前区间集合存在交集，则将交集部分取出，并且计算该部分的罚款总额将该路口的维修时间段加入当前区间集合，维护集合的增序，重复步骤3，直至处理完所有路口

# 将每个路口按照维修起始时间递增排序sorted_intervals = sorted(intervals, key=lambda x: x[0])# 初始：空集合 s，罚款总额 total = 0s = 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_taskselse: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 taskelse:break//对剩余的非必须任务按照所需资源从大到小排序。sort(optional_tasks, by resource needed, descending)//依次给非必须任务分配资源，直到分配完毕或无法完成任务。for each task in optional_tasks:if task can be completed:allocate resources to taskelse:break

标签：