题目

*7、现在有9件物品，每件物品的价值分别为20，20，30，50，60，70，80，90，90。需要把这些物品根据价值进行分组，且组数尽量少，但每组最多只能包含两件物品，且价值和不能超过100，请问：最少的分组数目是多少？（不需要填单位只需要填数字）

题目解答

答案

将9件物品按价值分组，每组最多2件且总价值不超过100。 1. 价值90的物品需单独成组（2组）。 2. 价值80的物品与价值20的物品组合（1组）。 3. 剩余物品（20, 30, 50, 60, 70）可组合为： - (70, 30) - (60, 20) - (50) **总组数：** 2（90）+ 1（80, 20）+ 1（70, 30）+ 1（60, 20）+ 1（50）= 6 **答案：** $\boxed{6}$

解析

考查要点：本题主要考察贪心算法的应用，通过合理配对物品价值，使得组数最少。关键在于优先处理高价值物品，并尽可能与其他物品配对，同时满足总和不超过100的条件。

解题核心思路：

优先处理无法配对的高价值物品：价值超过50的物品（如90、80、70等）必须单独或与其他低价值物品配对。
配对策略：将剩余的高价值物品与低价值物品配对，使总和接近100但不超过。
剩余物品处理：无法配对的物品单独成组。

破题关键点：

两个90必须单独成组（无法与其他物品配对而不超过100）。
80需与20配对（唯一可行的组合）。
剩余物品通过最优配对减少组数。

步骤1：处理最高价值的物品

两个90：无法与其他物品配对（90+20=110>100），因此各自单独成组，共2组。

步骤2：处理次高价值的物品

80：与20配对（80+20=100），形成1组。

步骤3：处理剩余高价值物品

70：与30配对（70+30=100），形成1组。
60：与20配对（60+20=80），形成1组。

步骤4：处理剩余物品

50：无法与其他物品配对（50+30=80，但30已被使用），因此单独成组，形成1组。

总组数：2（90） + 1（80,20） + 1（70,30） + 1（60,20） + 1（50） = 6组。