举个贪心算法的python例子
时间: 2023-02-24 19:11:25 浏览: 129
下面是一个贪心算法的简单 Python 代码例子,它解决了一个选择工作的问题:
```
# 假设有一些工作,每个工作有开始时间和结束时间
jobs = [(0, 6), (1, 4), (3, 5), (3, 8), (4, 7), (5, 9), (6, 10), (8, 11)]
# 按照结束时间排序
jobs.sort(key=lambda x: x[1])
# 初始化一个计数器,表示当前选择的工作数
count = 0
# 初始化一个时间点,表示当前可用的最早结束时间
cur_time = 0
# 遍历每个工作
for job in jobs:
# 如果当前工作的开始时间大于当前可用的最早结束时间
# 那么可以选择该工作
if job[0] >= cur_time:
count += 1
cur_time = job[1]
# 输出最多可以选择的工作数
print(count)
```
运行结果是:4,表示可以选择 4 个工作。
相关问题
再举一个贪心算法的python例子
### 回答1:
好的,下面是一个关于贪心算法的 Python 例子:
假设我们要选择一组物品以获得最大价值,其中每件物品都有一个体积和一个价值。我们可以使用贪心算法,每次选择价值密度最高的物品。
以下是代码实现:
```
def max_value(items, max_weight):
# 将物品按价值密度从大到小排序
items = sorted(items, key=lambda x: x[1] / x[0], reverse=True)
total_value = 0
total_weight = 0
for item in items:
if total_weight + item[0] <= max_weight:
total_weight += item[0]
total_value += item[1]
return total_value
# 测试
items = [(2, 3), (3, 4), (4, 5), (5, 6)]
max_weight = 7
print(max_value(items, max_weight)) # Output: 10
```
在这个例子中,我们选择了价值密度最高的物品,直到不能再选择任何物品为止,以获得最大的价值。
### 回答2:
一个简单的贪心算法的例子是找零钱问题。假设有1元、5元、10元、50元、100元的纸币,需要找给顾客一个金额为n的零钱,假设n为正整数。贪心算法的思路是尽可能多地使用大面值的纸币,从而减少纸币的数量。
下面是一个用Python实现的找零钱问题的贪心算法例子:
```python
def change(n):
bills = [100, 50, 10, 5, 1] # 纸币面值数组
result = [] # 存放结果的数组
for bill in bills:
count = n // bill # 计算该面值纸币的张数
n = n % bill # 更新剩余金额
for _ in range(count):
result.append(bill) # 将该面值纸币添加到结果数组中
if n == 0:
break # 当剩余金额为0时跳出循环
return result
# 测试
print(change(173)) # 输出: [100, 50, 10, 10, 1, 1, 1]
print(change(55)) # 输出: [50, 5]
print(change(101)) # 输出: [100, 1]
print(change(30)) # 输出: [10, 10, 10]
```
以上代码中,`bills`数组存放了纸币的面值,通过依次遍历这些面值,计算出当前面值纸币的张数,并将其添加到结果数组中。每次计算完后更新剩余金额,并判断是否为0,如果是则跳出循环。最后返回结果数组。
通过贪心算法,该例子有效地使用大面值纸币,尽量减少了纸币的数量,得到了满足条件的找零方案。
### 回答3:
贪心算法是一种解决问题的策略,它总是做出在当前看来最好的选择,而不考虑后续的结果。
以下是一个使用贪心算法解决找零钱问题的Python例子:
假设给定不同面额的货币 coins = [1, 5, 10, 20, 50, 100],以及需要找零的金额 amount = 193。
首先,我们需要找零的金额是最大面额的货币无法满足的,即无法使用100的货币。而使用最小面额的货币凑够193是不现实的,因此我们可以尝试使用较大面额的货币。
从上面的面额列表中选择最大的面额 100,我们可以计算出193/100得到1,意味着我们可以使用1个100的货币。现在剩下的金额是193 - 100 = 93。
继续选择下一个最大的面额 50,我们可以计算出93/50得到1,即我们可以使用一个50的货币。剩下的金额是93 - 50 = 43。
继续选择下一个最大的面额 20,我们可以计算出43/20得到2,即我们可以使用两个20的货币。剩下的金额是43 - 20 * 2 = 3。
接下来选择一个最大面额 5,我们可以计算出3/5得到0,因此无法使用任何5的货币。但我们还有其他面额的货币没有尝试过。
继续选择下一个最大的面额 1,我们可以计算出3/1得到3,即我们可以使用3个1的货币。最终剩下的金额是3 - 1 * 3 = 0。
通过贪心算法,我们得出总共需要 2 个20的货币,1 个50的货币,1 个100的货币,以及 3 个1的货币来凑够193的金额。
虽然贪心算法可以有效解决一些问题,但它并不一定总能给出最优解。在一些情况下,贪心算法可能会得到次优解或者根本无法得到符合要求的解。因此在使用贪心算法时,需要仔细考虑问题的特性和要求。
tsp问题贪心算法python代码实例
TSP(Traveling Salesman Problem)问题是一个经典的组合优化问题,涉及到寻找一条经过所有城市恰好一次的最短路径。贪心算法是一种启发式搜索策略,但它并不保证一定能找到全局最优解。下面是使用Python实现的一种简单贪心算法的示例,它每次选择距离当前位置最近的城市作为下一站,直到遍历完所有城市。
```python
import sys
# 假设我们有一个列表表示城市的坐标,如[(0,0), (1,1), (2,2)]
def nearest_city(cities, current_city):
min_distance = sys.maxsize
next_city = None
for city in cities:
if city != current_city and distance(current_city, city) < min_distance:
min_distance = distance(current_city, city)
next_city = city
return next_city
def distance(city1, city2):
# 这里假设每个城市都是二维坐标,使用欧几里得距离计算
return ((city1[0] - city2[0]) ** 2 + (city1[1] - city2[1]) ** 2) ** 0.5
def greedy_tsp(cities):
tour = [cities[0]] # 从第一个城市开始
current_city = cities[0]
for _ in range(len(cities)-1):
next_city = nearest_city(cities, current_city)
tour.append(next_city)
current_city = next_city
# 回到起点完成环路
tour.append(tour[0])
return tour
# 示例用法
cities = [(0, 0), (1, 4), (3, 2), (7, 6), (5, 9)]
print("Greedy TSP Tour:", greedy_tsp(cities))
```
这个例子中的贪心算法并不是TSP的精确解决方案,因为它可能会导致局部最优而不是全局最优。对于复杂的问题,比如TSP,更常见的做法是使用动态规划或者混合智能算法(如遗传算法、模拟退火等)。如果你对如何解决实际的TSP问题有兴趣,这些算法会更适合。
阅读全文