备战蓝桥杯Day28 - 贪心算法

一、贪心算法

贪心算法（Greedy Algorithm）是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是全局最好或最优的算法。贪心算法在有最优子结构的问题中尤为有效。最优子结构指的是问题的最优解可以由子问题的最优解有效地构造出来。贪心算法与动态规划不同，它自顶向下做出贪心选择，不做回溯。

贪心算法的基本思路是：

1. 建立数学模型来描述问题。
2. 把求解的问题分成若干个子问题。
3. 对每一子问题求解，得到子问题的局部最优解。
4. 把子问题的局部最优解合成原来问题的一个解。

希望利用贪心算法得到问题的整体最优解，必须注意两条性质：

• 贪心选择性质：这是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。贪心选择是采用从顶向下、以迭代的方式做出相继选择，每做一次选择就将所求问题简化为一个规模更小的子问题。
• 最优子结构性质：当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用贪心算法或动态规划算法求解的关键特征。

贪心算法的优缺点如下：

• 优点：算法简单，效率高，省去了为找最优解要穷尽所有可能而必须耗费的大量时间。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题它能产生整体最优解或者是整体最优解的近似解。
• 缺点：因为它并不从整体最优上加以考虑，它在某些情况下所求得的解可能不是整体最优解，只是某种意义上的局部最优解。

二、找零问题 

？假设商店老板需要找零n元钱，钱币的面值有：100元、50元、20元、5元、1元，如何找零使得所需钱币的数量最少。

=>思路：

1、利用贪心算法，每次找最优解，先找面值最大的张数，因为面值最大，所需要的张数就会小

2、通过对要找零的钱数取余，再去寻找下一个面值最大的张数，这样循环实现。

代码实现：

t = [100, 50, 20, 5, 1]


def change(t, n):
    m = [0 for _ in range(len(t))]  # 通过列表推导式定义面值所对应的张数
    for i, money in enumerate(t):
        m[i] = n // money
        n = n % money
    return m, n


print(change(t, 376))

三、背包问题 - 分数背包

？问题描述

一个小偷在某个商店发现有n个商品，第i个商品价值v元，重w千克。他希望拿走的价值尽量高，但他的背包最多只能容纳W千克的东西。他应该拿走哪些商品?

商品1: V1=60  W1=10

商品2: V2=100 W2=20 

商品3: V3=120 W3=30

背包容量:W=50

分数背包: 对于一个商品，小偷可以拿走其中任意一部分。(商品为金砂)

问题思路

通过比较每一个商品的单价来确定要优先拿哪一个商品，拿到商品后将商品数量置为1，将背包的重量减少，计算商品价值综合，此通过循环比较来实现。

在开始算法之前先对商品的单价进行排序，用到了lambda匿名函数，对物品的价格，重量循环便利的时候用到了enumerate函数。

代码实现：

goods = [(60, 10), (120, 30), (100, 20)]
# 先将商品的单价从大到小排序
goods.sort(key=lambda x: x[0]/x[1], reverse=True)


def fractional_backpack(goods, w):
    m = [0 for _ in range(len(goods))]   # 创建列表记录带走商品的数量
    total_val = 0
    for i, (price, weight) in enumerate(goods):
        if w > weight:   # 背包有足够空余的空间带走商品
            m[i] = 1
            total_val += price  # 更新价格和重量
            w -= weight
        else:
            m[i] = w/weight
            total_val += price * m[i]   #计算带走几分之几的价格
            w = 0
            break
    return  total_val, m


print(fractional_backpack(goods, 50))

ps：

lambda函数

lambda 函数是 Python 中的一个轻量级的匿名函数，它允许你快速定义一个只有一行表达式的简单函数。lambda 函数没有自己的名称，因此也被称为匿名函数。它主要用于需要一个函数作为参数的场合，而无需显式地定义一个单独的函数。

lambda 函数的基本语法如下：

• arguments 是 lambda 函数的参数，可以有一个或多个，用逗号分隔。
• expression 是 lambda 函数的返回值，只能有一个表达式。

示例：

# 定义一个简单的 lambda 函数，它接受两个参数并返回它们的和  
add = lambda x, y: x + y  
  
# 使用 lambda 函数  
result = add(3, 4)  
print(result)  # 输出: 7

在这个例子中，add 是一个 lambda 函数，它接受两个参数 x 和 y，并返回它们的和。然后我们调用这个 lambda 函数，传入 3 和 4，得到结果 7。

lambda 函数经常与 Python 的内置函数如 map(), filter(), reduce() 等一起使用，这些函数接受一个函数作为参数，并对序列进行某种操作。

例如，使用 map() 函数和 lambda 函数来将列表中的每个元素平方：

numbers = [1, 2, 3, 4, 5]  
squared = map(lambda x: x ** 2, numbers)  
print(list(squared))  # 输出: [1, 4, 9, 16, 25]

在这个例子中，lambda x: x ** 2 是一个简单的 lambda 函数，它接受一个参数 x 并返回 x 的平方。我们使用 map() 函数将这个 lambda 函数应用到 numbers 列表的每一个元素上，得到一个新的迭代器 squared，然后将其转换为列表输出。

虽然 lambda 函数很有用，但它并不适合定义复杂的函数逻辑。对于更复杂的函数，应该使用 def 关键字来定义具名的函数。

 enumerate函数

enumerate() 是 Python 的内置函数，用于将一个可遍历的数据对象（如列表、元组或字符串）组合为一个索引序列，同时列出数据和数据下标，一般用在 for 循环当中。

enumerate() 函数的语法如下：

参数说明：

• iterable：一个可遍历的对象，如列表、元组或字符串。
• start（可选）：计数起始值，默认为0。

enumerate() 函数返回的是一个枚举对象，它生成由数据对象的元素和其下标（默认从0开始）组成的元组。

下面是一个使用 enumerate() 函数的简单示例

# 创建一个列表  
fruits = ['apple', 'banana', 'cherry']  
  
# 使用 enumerate() 函数遍历列表  
for index, fruit in enumerate(fruits):  
    print(f"Index {index}: {fruit}")

输出将会是：

Index 0: apple  
Index 1: banana  
Index 2: cherry

在这个例子中，enumerate(fruits) 为列表中的每个元素生成了一个元组，其中包含元素的索引和值。然后，for 循环将这两个值分别赋值给 index 和 fruit 变量，并打印出来。

如果你想要从1开始计数，而不是默认的0，你可以将 start 参数设置为1：

# 创建一个列表  
fruits = ['apple', 'banana', 'cherry']  
  
# 使用 enumerate() 函数遍历列表，从1开始计数  
for index, fruit in enumerate(fruits, start=1):  
    print(f"Index {index}: {fruit}")

输出将会是：

Index 1: apple  
Index 2: banana  
Index 3: cherry

这样，enumerate() 函数就可以很方便地在遍历序列的同时获取到元素的索引。

学习碎碎念

总是急着想要一下就成为很厉害的人，但是没有脚踏实地的努力和日复一日的学习都是空想！一步一步的来吧，不一定慢慢来，但要沉下心一步一步的来 。

“请深耕细作自己，长成一帜独树，欣欣浇灌，独当天地。”