基础题库

在货币兑换问题中，如果我们有多种面值的货币，并且想要用最少数量的货币凑齐某个金额，我们应该采用哪种策略？

贪心算法是一种动态规划算法的特殊情况。

贪心算法可以用于解决分数背包问题。

贪心算法在解决旅行商问题（TSP）时，总是能找到最短路径。

贪心算法的时间复杂度总是优于动态规划算法。

在一次拍卖会上，有 𝑛n 件物品和 𝑚m 位买家，每位买家都有一个最大可支付金额，每件物品也有一个起拍价格。每件物品会从起拍价格开始，然后所有还有钱的人都会互相竞价，直到只有一个人的剩余钱数买得起为止。如何分配物品给买家以使得收益最大化？

一个班级有n个学生参加了期末考试，现在你作为老师需要将这些学生分成若干个小组，每个小组的最低分和最高分之差不得超过x分。请问，按照这个标准，最少需要分成多少个小组？

给定N堆纸牌，编号为1到N。每堆上有若干张纸牌，纸牌的总数是N的倍数。你可以从任意一堆上取若干张纸牌，然后按规定移动。移动规则如下：从编号为1的堆上取的纸牌，只能移到编号为2的堆上；从编号为N的堆上取的纸牌，只能移到编号为N-1的堆上；其他堆上取的纸牌，可以移到相邻的左边或右边的堆上。目标是通过最少的移动次数，使得每堆上的纸牌数量相同。如何实现？

在一款策略游戏中，玩家需要保护一个果园免受入侵者的袭击。果园被划分为6行60列的网格。入侵者会在某一行的最右端出现，每秒钟向左移动一个格子。玩家可以在任何行的最左端放置一个滚动的保护球，这个保护球能瞬间消灭同一行内的所有入侵者。如果任何一个入侵者到达了果园的最左端，那么游戏就会结束。现在有n个入侵者即将到来，每个入侵者都有确切的出现时间和行数。请问，为了保护果园，玩家使用最少数量的保护球的方案是什么？

一位运动员准备参加十项全能比赛，他已经估计出了自己参加每项比赛可以得到的分数，但是由于时间限制，他只能选择其中的k项参加。为了获得最高的总分，他应该如何选择比赛项目？