贪心典型应用：活动选择与背包
较难2贪心算法实战：如何安排活动最多、背包最值钱？
你有没有遇到过这样的烦恼？一天有好多活动想去参加，可时间冲突，只能选一部分；或者你有个书包，想装进最值钱的东西，但每种东西可以只拿一部分。贪心算法就是帮你做出“当前最好选择”的方法，它每一步都挑眼前最有利的，最终得到很好的结果。今天我们就用两个经典问题来学会它。
活动选择：怎样参加最多活动？
问题：一天有多个活动，每个活动有开始时间和结束时间。你只能参加时间不重叠的活动，怎么选才能参加的数量最多？
贪心策略：每次选结束时间最早的活动。因为结束早，后面的时间更充裕，就有机会参加更多活动。
为什么选结束最早就对了？
想象你从早上8点到晚上10点，有一堆活动：
- 活动A：8:00 - 9:00
- 活动B：8:30 - 10:00
- 活动C：9:30 - 10:30
如果先选A（最早结束8:00-9:00），剩下时间可以选C（9:30-10:30），一共2个。
如果先选B（8:30-10:00），整天只能参加这一个。
所以选最早结束的活动，给后面留出最多时间。
换个例子更好懂
比如你和朋友约好做几件事：
- 看电影（1点开始，3点结束）
- 打篮球（2点开始，4点结束）
- 写作业（3点开始，5点结束）
- 吃火锅（0点开始，6点结束）
按结束时间排序：看电影（结束3点）→ 打篮球（结束4点）→ 写作业（结束5点）→ 吃火锅（结束6点）。
选结束最早的“看电影”，然后下一个只能在3点之后开始——剩下“写作业”（3-5点）可选。再下一个只能在5点之后——没活动了。一共2个。
如果先选“吃火锅”（0-6点），只能参加这一个。贪心帮我们找到最多2个活动。
Python代码实现
def max_activities(activities):
# activities: 列表，每个元素为 (开始时间, 结束时间)
activities.sort(key=lambda x: x[1]) # 按结束时间升序排序
count = 0
last_end = 0 # 上一个选中的活动的结束时间
for start, end in activities:
if start >= last_end: # 如果当前活动开始时间不早于上一个结束
count += 1
last_end = end
return count
# 测试
acts = [(1,3), (2,4), (3,5), (0,6)]
print("最多能参加的活动数：", max_activities(acts)) # 输出2
部分背包问题：怎样装最值钱？
问题：你有一个容量固定的背包，有若干种物品（每种有重量和价值），而且物品可以只拿一部分（比如半块黄金、半袋米）。怎样装能让总价值最大？
贪心策略：每次选单位重量价值最高的物品，优先拿它，直到背包装满。
单位价值是什么？
单位价值 = 价值 ÷ 重量。就是“每斤值多少钱”。
比如黄金：重量10斤，价值600元，单位价值 = 600/10 = 60元/斤
白银：20斤，价值800元，单位价值 = 800/20 = 40元/斤
钻石：30斤，价值900元，单位价值 = 900/30 = 30元/斤
显然先拿黄金最划算。
生活例子：食堂打饭
你有一个饭盒容量500毫升。三种菜：
- 红烧肉：200毫升，热量800卡（单位热量4卡/毫升）
- 青菜：100毫升，热量200卡（单位热量2卡/毫升）
- 米饭：300毫升，热量450卡（单位热量1.5卡/毫升）
贪心：先装红烧肉（全部200毫升，得800卡），剩余容量300毫升；再装青菜（全部100毫升，得200卡），剩余200毫升；最后装米饭（只能装200/300 = 2/3份，得450×2/3 = 300卡）。总热量 = 800+200+300 = 1300卡。
如果先装米饭（全部300毫升，得450卡），剩余200毫升装红烧肉（200毫升，得800卡），总热量1250卡，不如贪心方案。
Python代码实现
def fractional_knapsack(items, capacity):
# items: 列表，每个元素为 (重量, 价值)
# 按单位价值（价值/重量）降序排序
items.sort(key=lambda x: x[1] / x[0], reverse=True)
total_value = 0
for weight, value in items:
if capacity >= weight:
total_value += value
capacity -= weight
else:
fraction = capacity / weight
total_value += value * fraction
break
return total_value
# 测试
items = [(10,60), (20,100), (30,120)] # (重量, 价值)
cap = 50
print("最大价值：", fractional_knapsack(items, cap)) # 输出240.0
新手常犯的错误
-
活动选择的排序搞错了
有的人按开始时间排序，或者按活动时长排序，这样可能得不到最多活动。必须按结束时间最早的顺序选。 -
部分背包问题中搞混“单位价值”和“总价值”
不能只看总价值最高的物品，要看“每斤值多少钱”。比如钻石总价值120很高，但单位价值只有4，不如黄金的6。所以先拿黄金。 -
忘记部分背包和0-1背包的区别
- 部分背包：物品可以切分，贪心有效。
- 0-1背包：物品只能整个拿或不拿，贪心不一定最优（比如容量50，物品A: (30,60)单位2，B: (20,100)单位5，C: (20,90)单位4.5，贪心先拿B和C得190，但拿A+C得150，而最优是B+A得160？需验证——其实贪心在这情况不一定对）。所以0-1背包要用动态规划。
很多同学把0-1背包也当部分背包去贪心，导致答案错误。
-
排序后没考虑容量可能装不下整个物品
在部分背包中，最后一种物品可能只装一部分，代码中要用fraction计算，不能直接total_value += value。
完整可运行的代码示例
下面把活动选择和部分背包合在一起展示，并加入更多测试数据。
# ---------- 活动选择 ----------
def max_activities(activities):
# activities: 元组列表 (开始, 结束)
activities.sort(key=lambda x: x[1]) # 按结束时间升序
count = 0
last_end = 0
for start, end in activities:
if start >= last_end:
count += 1
last_end = end
return count
# 测试活动
acts = [(1,3), (2,4), (3,5), (0,6), (4,7), (5,8)]
print("最多活动数：", max_activities(acts)) # 输出3 (选(1,3),(3,5),(5,8))
# ---------- 部分背包 ----------
def fractional_knapsack(items, capacity):
# items: 元组列表 (重量, 价值)
items.sort(key=lambda x: x[1] / x[0], reverse=True) # 按单位价值降序
total_value = 0
for weight, value in items:
if capacity >= weight:
total_value += value
capacity -= weight
else:
fraction = capacity / weight
total_value += value * fraction
break
return total_value
# 测试物品
stuff = [(10,60), (20,100), (30,120)] # (重量,价值)
cap = 50
print("最大价值：", fractional_knapsack(stuff, cap)) # 240.0
# 再加一个测试：水果装袋
fruits = [(1,5), (2,8), (3,10)] # 重量kg, 价值元
bag = 4
print("水果最大价值：", fractional_knapsack(fruits, bag)) # 单位价值:5,4,3.33 → 先拿1kg水果(5),再拿2kg(8),最后拿1/3的3kg(3.33) → 5+8+3.33=16.33
运行结果：
最多活动数： 3
最大价值： 240.0
水果最大价值： 16.333333333333332
还想学更多？
贪心算法还有很多经典应用：
- 哈夫曼编码：用最短的二进制码表示字符，节省存储空间。
- 最小生成树（Prim、Kruskal算法）：修路怎样最省钱。
- 加油站问题：开车跑长途，怎样加油最少。
但贪心不是万能的，遇到0-1背包、**找零钱（某些币值）**等题目，就需要动态规划或回溯法。建议你学完贪心后，再接触动态规划，对比两者的区别。
试一试：如果活动可以中断（参加一半就走），还能用贪心吗？想一想，欢迎自己写代码验证！
例题精讲
在活动选择问题中，贪心算法通常依据哪个原则来选择活动？
对于部分背包问题（物品可分），贪心算法应按照哪个指标进行排序？
在活动选择问题中，如果按照开始时间最早的原则进行贪心选择，同样可以得到活动数量最多的最优解。
以下代码是活动选择问题的贪心实现，请补全循环中判断活动是否可选的空缺部分。
def activity_selection(start, finish):
n = len(start)
activities = sorted(zip(start, finish), key=lambda x: x[1]) # 按结束时间排序
selected = [activities[0]]
last_finish = activities[0][1]
for i in range(1, n):
if activities[i][0] ___ last_finish: # 填空处
selected.append(activities[i])
last_finish = activities[i][1]
return selected以下代码是实现部分背包问题的贪心算法，请补全排序的 key 以及循环中装入物品的部分。
def fractional_knapsack(weights, values, capacity):
n = len(weights)
items = [(values[i], weights[i], values[i]/weights[i]) for i in range(n)]
items.sort(key=lambda x: ___, reverse=True) # 填空1
total_value = 0.0
for value, weight, ratio in items:
if capacity >= weight:
total_value += value
capacity -= weight
else:
total_value += ___ # 填空2
break
return total_value