每日一题——最小测试用例集覆盖问题

最小测试用例集覆盖问题（C语言实现）

问题描述

假设我们有一系列测试用例，每个测试用例会覆盖若干个代码模块。

我们使用一个二维数组来表示这些测试用例的覆盖情况：

• 如果某个测试用例 i 能覆盖代码模块 j，则数组中 tests[i][j] = 1；
• 否则为 0。

目标是：找出一个最小数量的测试用例集合，使得这些用例组合起来能覆盖所有代码模块。

如果不存在这样的集合，则输出 -1。

输入描述

• 第一行输入两个整数 n 和 m，分别代表测试用例总数和代码模块总数。
• 接下来的 n 行，每行输入 m 个数字 0 或 1，表示该测试用例对各个模块的覆盖情况。

参数范围

• 所有输入为 0 或 1
• 1 ≤ n ≤ 20（因为需要枚举子集）

---

输出描述

• 能覆盖所有代码模块的最小用例集合的大小；
• 如果不存在这样的集合，输出 -1。

---

示例

示例1

输入：
3 2
1 0
1 0
1 0输出：
-1

说明：所有用例都只覆盖模块0，无法覆盖模块1，返回 -1。

示例2

输入：
4 4
1 0 1 0
0 1 0 1
1 1 0 0
0 0 1 1输出：
2

说明：用例0和1组合可以覆盖所有模块，也可以是用例2和3，总数最小是2。

示例3

输入：
3 2
1 0
0 1
1 1输出：
1

说明：用例2本身就可以覆盖所有模块。

---

解题思路

1. 使用位掩码表示测试用例覆盖情况：
   将每个测试用例的覆盖情况转化为一个整数，二进制的每一位表示对应模块是否被覆盖。

2. 计算目标掩码：
   所有模块都被覆盖时，目标掩码为 (1 << m) - 1，即低 m 位全是1。

3. 暴力枚举所有子集：
   总共有 $2^n$ 个测试用例子集，检查每个子集是否能覆盖所有模块。

4. 更新最小数量：
   如果当前子集的按位或结果等于目标掩码，说明它能覆盖所有模块，更新最小用例数量。

---

C语言实现（附详细注释）

#include <stdio.h>
#include <stdlib.h>#define MAX_N 20int min(int a, int b) {return a < b ? a : b;
}int main() {int n, m;scanf("%d %d", &n, &m);int tests[MAX_N] = {0};  // 每个测试用例的掩码表示（最多20个）// 读取测试用例数据并转为位掩码for (int i = 0; i < n; ++i) {int mask = 0;for (int j = 0; j < m; ++j) {int x;scanf("%d", &x);if (x == 1) {mask |= (1 << j);  // 将第j位设为1，表示覆盖第j个模块}}tests[i] = mask;}int target = (1 << m) - 1;  // 所有模块都被覆盖时的目标掩码int ans = n + 1;  // 初始设为比最大用例数多1（无效值）// 枚举所有可能的测试用例子集（从1到2^n-1）for (int subset = 1; subset < (1 << n); ++subset) {int union_mask = 0;int count = 0;for (int i = 0; i < n; ++i) {if (subset & (1 << i)) {  // 如果第i个用例在子集中union_mask |= tests[i];  // 累加覆盖模块count++;  // 子集中的用例个数}}// 如果该子集能覆盖所有模块，尝试更新最小值if (union_mask == target) {ans = min(ans, count);}}// 如果未找到有效子集，则返回-1if (ans > n) {printf("-1\n");} else {printf("%d\n", ans);}return 0;
}

---

总结

• 使用位运算可以高效表示模块覆盖情况；
• 暴力枚举适用于数据范围较小（如测试用例≤20）的问题；
• 注意边界条件，如所有模块都无法覆盖时应返回 -1。