贪心算法适用场景判断测试卷

Q1:姓名

Q2:班级

Q3:零钱兑换（普通人民币场景）：你要凑出36元，纸币面额只有1元、5元、10元、20元。你每次都拿当前能拿的最大面额纸币，想要最终拿出的纸币总数量最少。请问这个问题可以用贪心解决。

Q4:特殊零钱兑换（贪心失效场景）：假设某个国家纸币面额只有1元、3元、4元。现在要凑出6元。如果每次都优先拿最大面额的钱（先拿4元），最终钞票数量不是最少的。请问该问题可以用贪心解决。

Q5:选课安排问题：一天里有很多节兴趣课，所有课时间互相冲突，同一时间只能上一节课。每节课都有固定的开始时间和结束时间。我们每次选择「最先结束」的一节课去上，尽可能多上几节课。请问该问题可以用贪心得到最多上课数量。

Q6:装书包问题（对应01背包，零基础易懂）：你的书包最多只能装10斤东西。现在有几件零食和书本，每件东西只能整件带、不能拆分。你想带的东西总价值最高。如果你每次只挑「单位重量最值钱」的东西先装，无法保证最后总价值最大。请问该问题可以用贪心解决。

Q7:路灯覆盖问题（区间覆盖通俗版）：一条笔直的小路从起点到终点，需要全部装上路灯照亮整条路。现在有很多可选的路灯安装位置，每个路灯能照亮一段连续的路面。每次选择「能覆盖当前路口、且照得最远」的路灯，用最少的路灯照亮整条路。请问可以用贪心解决。

Q8:分饼干问题：有一群小朋友，每个人饭量不一样（想吃的饼干最小尺寸不同）；有一堆大小不同的饼干，一块饼干只能给一个人吃。我们的目标是：让最多的小朋友吃到饼干。策略是：用最小的刚刚好满足小朋友的饼干去分配。请问可以用贪心解决。

Q9:爬山找近路（贪心最短路径失效）：你要从山脚走到山顶，路上有很多分叉路口。你每次走路只选「眼前最近、最短的一小段路」走。但这种走法很容易走进绕远路、死胡同，不一定是全程最短路线。请问从山脚到山顶找最短路径，可以用贪心解决。

Q10:数字拼大数（简单贪心误区）：给你两个数字3和30，要求把两个数字拼起来，变成一个最大的数。如果单纯看单个数字大小，3比30大，会拼成330，但实际最大数是303。只靠“选当前最大单个数字”的策略行不通。请问该问题可以用普通贪心解决。

Q11:排队打水问题：有很多同学排队接水，每个人接水需要的时长不一样。想要让所有人总的等待时间最少。策略是：每次让接水最快、用时最短的同学先接水。请问可以用贪心得到最优结果。

Q12:打扫教室分工问题：有3个同学打扫教室，有好几项打扫任务，每一项任务耗时不同、不能拆分。为了让大家结束时间尽量一致、不有人累死、有人闲着。策略是：每次把当前最耗时的任务，分给目前最闲的同学。该策略能得到最优均衡方案，可以用贪心。