贪心算法 Greedy Algorithm¶

贪心算法是指在对问题的求解过程中，总是做出当前看来最好的选择而不从总体上进行考虑。

贪心算法不能保证得到问题的最优解，但是在某些问题上，贪心算法得到的就是最优解。

贪心算法的主要思想¶

若局部最优解可以得到整体最优解，则可以使用贪心算法。贪心算法的关键是找到该贪的东西。

贪心算法一般用于最优化问题。但是相当一部分最优问题不能用贪心算法，而需要使用 动态规划 方法。

例题¶

1.找零问题¶

问题描述 ：假设商店老板需要找零n元，老板拥有以下面额的钱币（假设老板拥有各类钱币无限个/张）100、50、20、5、1，请问如何找零所需要的钱币张数/个数最少？

2.分数背包问题¶

问题描述 ：一个小偷在商店发现n个物品，第i个物品价值为 \( v_i \) 元，重量为 \( w_i \) 。他希望拿走的东西价值尽可能高，但是他的背包只能装 \( W \) 千克的东西，他应该拿走哪些商品？
（可以拿走物品的一部分，即能拿分数个但且每件商品只有此一件。）

例如：

商品编号	\( v_i \)	\( w_i \)
1	60	10
2	100	20
3	120	30

背包容量W为50。

3.数字拼接问题¶

问题描述 ：有n个非负整数，将其按照字符串拼接的方式拼接成最大的一个整数。

例：
32，94，128，1286，6，71

# python
numbers = ["32","94","128","1286","6","71"]

def number_connection(numbers: list):
    for i in range(len(numbers) - 1 , 0 , -1):
        for j in range(i):
            if int(numbers[j] + numbers[j+1]) < int(numbers[j+1] + numbers[j]):
                numbers[j] , numbers[j+1] = numbers[j+1] , numbers[j]
    return "".join(numbers)

if __name__ == "__main__":
    print(number_connection(numbers))

4.活动选择问题¶

问题描述 ：假设有n个活动，这些活动要占用同一场地，而场地在某时刻只能供一个活动使用。
每个活动都有一个开始时间 \( s_i \) 和结束时间 \( f_i \) ,表示活动在 \( [ s_i , f_i ) \) 区间占用场地。
问：安排哪些活动能够使该场地举办的活动个数最多？

\( i \)	\( s_i \)	\( f_i \)
1	1	4
2	3	5
3	0	6
4	5	7
5	3	9
6	5	9
7	6	10
8	8	11
9	8	12
10	2	14
11	12	16

# python
activity = [(1,4) , (3,5) , (0,6) , (5,7) , (3,9) , (5,9) , (6,10) , (8,11) , (8,12) , (2,14) , (12,16)]

def activity_selection(activity: list):
    # 贪结束时间最早的
    # 按结束时间从小到大排序
    activity.sort(key=lambda x: x[1])
    # 开始安排
    res = []
    startTime = 0

    for i in activity:
        if i[1] >= startTime:
            if  not res or res[-1][1] <= i[0]:
                res.append(i)
                startTime = i[1]
    print(res)
    return res

if __name__ == "__main__":
    activity_selection(activity)