Python实现贪心算法基础版详解

贪心算法-简单版

贪心算法的一般使用场景是给定一个列表ls, 让你在使用最少的数据的情况下达到或超过n.
我们就来使用上面讲到的这个朴素的例题来讲讲贪心算法的基本模板:

2-1.排序

既然要用最少的数据, 我们就要优先用大的数据拼, 为了实现这个效果, 我们得先给列表从大到小排序.

sorted(ls, reverse = True)
# 别忘了reverse = True从大到小

2-2.选择

我们需要遍历列表, 每次选出现在的元素, 记录当前总和和累加次数, 当总和大于等于n时, 结束循环.

tot = 0
cnt = 0
# 注意一个很容易错的地方, 这里的语句顺序不可改变!
for l in ls:
	tot += l
	if tot >= n:
		break
	cnt += 1

2-3.完整简单版模板

注释版:

# 输入
n = int(input())
ls = [int(i) for i in input().split()]

# 排序
sorted(ls, reverse = True)

# 主要算法, 摘大苹果
tot = 0
cnt = 0
for l in ls:
	tot += l
	if tot >= n:
		break
	cnt += 1

记忆版:

n = int(input())
ls = [int(i) for i in input().split()]
sorted(ls, reverse = True)
tot = 0
cnt = 0
for l in ls:
	tot += l
	if tot >= n:
		break
	cnt += 1

作者：无影无踪的青蛙