北京海淀区信息学竞赛 · 2024 北京市海淀区信息学竞赛（初赛）试题 第 15 题

有 $5$ 克，$25$ 克，$30$ 克，$50$ 克的砝码各若干个，从中共取 $n$ 个，每类砝码至少取 $1$ 个，50 克的砝码不能超过 $6$ 个，若总质量为 $1$ 千克，则 $n$ 的最小值为（　　）

这题其实是道整数规划题，但别被吓到：先算出最少要几个砝码，再往回凑。50 克最多拿 6 个，剩下 100 克用 30 和 25 凑，最后 5 克必须补一个 5 克砝码。

最容易掉进两个坑：一是忘了“每类至少取 1 个”这个硬约束，算出 2 个砝码就以为够了；二是把 50 克砝码当成可以无限用，直接凑 1000 克，结果 n 算出来只有 20 左右，完全违背题意。还有人选 C 或 D，是因为在凑 100 克时贪心地多用 30 克，导致总个数变多，却忘了 50 克上限是 6 个，这时候应该优先用 50 克把大缺口补上，再回头用 30 和 25 填余数。

这道题考查的是带约束的整数拆分（本质是简单的整数线性规划），核心概念就是：在给定上限和下限的前提下，用几种固定面值的物品凑出目标总量，并且要满足每类至少一个。命题人喜欢在这种题里埋两个坑：一是“每类至少取 1 个”，二是“50 克不能超过 6 个”，这两个条件同时存在，很容易让人先算出理论最小值，然后忘记回头检查约束。拿到题先想什么？先算理论下界：1000 克 ÷ 50 克 = 20 个，这是不考虑任何约束时的最小个数。但题目明确说 50 克最多 6 个，所以必须用更小的面值来补足。接下来从最大面值开始贪心：先拿 6 个 50 克，共 300 克，还差 700 克。再用 30 克去凑，700 ÷ 30 = 23 余 10，但 30 克不能单独凑出 10，而且 23 个 30 克加上之前的 6 个 50 克已经 78 个了，显然太多。换个思路：既然 50 克上限是 6 个，剩下的 700 克尽量用 30 克和 25 克，但还要保证 5 克至少一个。先留一个 5 克砝码，剩下 995 克。现在问题变成：用 30 克和 25 克凑 995 克，且 50 克已经用满 6 个。995 ÷ 30 = 33 余 5，余数正好是 5，但 5 克砝码已经预留了，所以不能再用 30 克去凑这个 5。再试 995 ÷ 25 = 39 余 20，20 也不是 5 的倍数。看来直接贪心不行，得调整 50 克的数量。尝试 5 个 50 克：250 克，剩 750 克。750 ÷ 30 = 25 余 0，完美！此时用了 5 个 50 克、25 个 30 克，共 30 个，还差一个 5 克砝码，总数 31 个。检查约束：每类至少一个？5 克有，25 克没用到，不行。再试 4 个 50 克：200 克，剩 800 克。800 ÷ 30 = 26 余 20，20 不是 5 的倍数。3 个 50 克：150 克，剩 850 克。850 ÷ 30 = 28 余 6，6 不是 5 的倍数。2 个 50 克：100 克，剩 900 克。900 ÷ 30 = 30 余 0，此时用了 2 个 50 克、30 个 30 克，再加一个 5 克砝码，共 33 个，但 25 克还是没用到。1 个 50 克：50 克，剩 950 克。950 ÷ 30 = 31 余 20，不行。0 个 50 克：1000 克，1000 ÷ 30 = 33 余 10，不行。回头重新规划：既然 25 克必须至少一个，那就先放一个 25 克，剩 975 克。975 ÷ 30 = 32 余 15，15 不是 5 的倍数。再放一个 25 克，剩 950 克，950 ÷ 30 = 31 余 20，不行。继续增加 25 克：三个 25 克，剩 925 克，925 ÷ 30 = 30 余 25，25 正好是一个 25 克，但这样 25 克总数变成 4 个，50 克还是 0 个，不行。换个角度：既然 50 克上限是 6 个，我们可以尝试 6 个 50 克 + 2 个 25 克 = 350 克，剩 650 克。650 ÷ 30 = 21 余 20，不行。6 个 50 克 + 3 个 25 克 = 400 克，剩 600 克。600 ÷ 30 = 20 余 0，完美！此时用了 6 个 50 克、3 个 25 克、20 个 30 克，共 29 个，还差一个 5 克砝码，总数 30 个。检查约束：每类至少一个？5 克有，25 克有，30 克有，50 克有，全部满足。50 克不超过 6 个？正好 6 个，满足。总质量？6×50 + 3×25 + 20×30 + 1×5 = 300 + 75 + 600 + 5 = 980 克，不对，少 20 克。刚才算错了：6 个 50 克是 300 克，3 个 25 克是 75 克，20 个 30 克是 600 克，加起来 975 克，再加 1 个 5 克是 980 克，还差 20 克。说明 20 个 30 克不对，应该用 21 个 30 克：21×30 = 630 克，加上 300 + 75 + 5 = 980 克，还是差 20 克。再试 6 个 50 克 + 4 个 25 克 = 450 克，剩 550 克。550 ÷ 30 = 18 余 10，不行。6 个 50 克 + 5 个 25 克 = 500 克，剩 500 克。500 ÷ 30 = 16 余 20，不行。6 个 50 克 + 6 个 25 克 = 550 克，剩 450 克。450 ÷ 30 = 15 余 0，完美！此时用了 6 个 50 克、6 个 25 克、15 个 30 克，共 27 个，再加 1 个 5 克砝码，总数 28 个。检查总质量：6×50 = 300，6×25 = 150，15×30 = 450，1×5 = 5，合计 905 克，不对，少 95 克。显然刚才的加法错了：6 个 50 克是 300，6 个 25 克是 150，15 个 30 克是 450，加起来 900，再加 1 个 5 克是 905 克，确实不够 1000 克。说明 15 个 30 克不对，应该用 20 个 30 克：20×30 = 600，300 + 150 + 600 + 5 = 1055 克，超了。再试 6 个 50 克 + 4 个 25 克 = 450 克，剩 550 克。550 ÷ 30 = 18 余 10，不行。6 个 50 克 + 3 个 25 克 = 400 克，剩 600 克。600 ÷ 30 = 20 余 0，此时用了 6 个 50 克、3 个 25 克、20 个 30 克，共 29 个，再加 1 个 5 克砝码，总数 30 个。总质量：300 + 75 + 600 + 5 = 980 克，还是差 20 克。看来 20 个 30 克不对，应该用 21 个 30 克：21×30 = 630，300 + 75 + 630 + 5 = 1010 克，超了。再试 6 个 50 克 + 5 个 25 克 = 500 克，剩 500 克。500 ÷ 30 = 16 余 20，不行。6 个 50 克 + 6 个 25 克 = 550 克，剩 450 克。450 ÷ 30 = 15 余 0，此时用了 6 个 50 克、6 个 25 克、15 个 30 克，共 27 个，再加 1 个 5 克砝码，总数 28 个。总质量：300 + 150 + 450 + 5 = 905 克，不对。重新审视：也许 50 克不必用满 6 个。尝试 5 个 50 克 = 250 克，剩 750 克。750 ÷ 30 = 25 余 0，此时用了 5 个 50 克、25 个 30 克，共 30 个，再加 1 个 5 克砝码，总数 31 个。总质量：250 + 750 + 5 = 1005 克，超了 5 克。再试 5 个 50 克 + 24 个 30 克 = 250 + 720 = 970 克，剩 30 克，再加 1 个 5 克砝码，总数 30 个，总质量 975 克，不够。5 个 50 克 + 25 个 30 克 = 1000 克，再加 1 个 5 克砝码，总数 31 个，总质量 1005 克，超了。5 个 50 克 + 24 个 30 克 + 1 个 25 克 = 250 + 720 + 25 = 995 克，再加 1 个 5 克砝码，总数 31 个，总质量 1000 克，完美！检查约束：每类至少一个？5 克有，25 克有，30 克有，50 克有，全部满足。50 克不超过 6 个？正好 5 个，满足。总质量 1000 克，满足。个数 31 个，是满足所有条件的最小值吗？再试 4 个 50 克 = 200 克，剩 800 克。800 ÷ 30 = 26 余 20，不行。4 个 50 克 + 25 个 30 克 = 200 + 750 = 950 克，剩 50 克，再加 1 个 5 克砝码，总数 31 个，总质量 955 克，不够。4 个 50 克 + 26 个 30 克 = 200 + 780 = 980 克，剩 20 克，不行。4 个 50 克 + 25 个 30 克 + 1 个 25 克 = 200 + 750 + 25 = 975 克，剩 25 克，再加 1 个 5 克砝码，总数 32 个，总质量 1000 克，但个数 32 大于 31。所以 31 个确实是满足所有条件的最小值。因此正确答案是 B。