举个贪心算法的python例子

下面是一个贪心算法的简单 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实现的找零钱问题的贪心算法例子：

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的金额。

虽然贪心算法可以有效解决一些问题，但它并不一定总能给出最优解。在一些情况下，贪心算法可能会得到次优解或者根本无法得到符合要求的解。因此在使用贪心算法时，需要仔细考虑问题的特性和要求。

贪心算法几个经典例子Python

以下是几个经典的贪心算法例子的 Python 代码：

1. 零钱兑换问题

'''
题目描述：给定一个整数金额和一些硬币，求出能够组成该金额的最少硬币数。

例如，当金额为 11 时，硬币面值为 [1, 2, 5]，应返回 3（5元硬币1枚，2元硬币2枚）。

思路：贪心策略是每次尽可能使用面值最大的硬币，直到金额为 0。

'''

def coin_change(coins, amount):
coins.sort(reverse=True)
count = 0
for coin in coins:
if amount == 0:
break
if coin <= amount:
count += amount // coin
amount = amount % coin
return count if amount == 0 else -1

2. 活动选择问题

'''
题目描述：假设有 n 个活动，每个活动都有一个开始时间和结束时间。选择一些活动，使得它们不冲突，且能够参加的活动数最多。

例如，有以下 6 个活动：
[ (1, 4), (3, 5), (0, 6), (5, 7), (3, 8), (5, 9) ]

其中，选择 (0, 6), (6, 7), (7, 8), (8, 9) 四个活动，即可参加的活动数最多。

思路：贪心策略是每次选择结束时间最早的活动，并且该活动与前面选择的活动不冲突。

'''

def activity_selection(activities):
activities.sort(key=lambda x: x[1])
selected = []
end_time = -1
for activity in activities:
if activity[0] >= end_time:
selected.append(activity)
end_time = activity[1]
return selected

3. 分糖果问题

'''
题目描述：给定两个列表，分别表示 n 个孩子的糖果数和 m 个糖果的大小。要求将糖果分给孩子，使得每个孩子最多只能分到一个糖果，并且尽可能多的孩子能够分到糖果。

例如，有 3 个孩子，糖果大小为 [1, 2, 3]，糖果数为 [1, 1]，则最多只能分配 2 个孩子，因为第三个孩子没有糖果可分。

思路：贪心策略是每次尽可能给糖果大小最小且能够满足该孩子的糖果。

'''

def candy(children, candies):
children.sort()
candies.sort()
i = j = 0
count = 0
while i < len(children) and j < len(candies):
if candies[j] >= children[i]:
count += 1
i += 1
j += 1
return count