解题思路

给定若干用例，每个用例覆盖若干接口；执行一个用例的耗时等于其覆盖到的所有接口耗时之和。选择一组用例，使得：

• 总耗时 ≤ T；
• 对每个接口 i，被覆盖的次数在 [1, S] 内；
• 总测试收益最大。接口 i 的收益取所选用例中“用例对接口测试收益”的最大值，即 max_j(p_i_j * w_i)；整体收益为所有接口收益之和。

核心算法：子集枚举（暴力搜索）

题目内容

在测试资源有限时，需从候选用例集中选择部分用例，在满足对待测接口的覆盖要求的前提下，最大化测试收益。

给定 $m$ 个接口，每个接口属性如下：

接口编号 $i$ ，取值范围 $[1,m]$

接口重要度 $w_i$ ，取值范围 $[1,5]$

接口耗时 $t_i$ ，取值范围 $[1,5]$

给定 $n$ 个用例，每个用例属性如下：

用例编号 $j$，取值范围 $[1,n]$

覆盖的[接口编号 $i$ ，发现该接口缺陷概率 p_i_j]集合(每个用例可覆盖多个接口,对每个接口的发现缺陷概率 p_i_j 为 $0$ ~ $1$ 之间，保留 $2$ 位小数)

约束：

给定总执行时间不超过 $T$

每个接口执行次数至少为 $1$ 次，不可超过 $S$ 次

任务：

定义“用例对接口测试收益”为 其发现该接口缺陷概率 p_i_j * 该接口重要度

定义每个接口的"接口测试收益"为，所有用例对该接口"用例对接口测试收益"的最大值

定义整体“总测试收益"为，所有接口"接口测试收益"的总和求最大化的"总测试收益"

输入描述

第一行: $T$ (总时长限制，$1≤T≤100$)、$S$ (单个接口执行次数限制，$1≤S≤5$ )、$m$ (接口数， $1≤m≤3$ )、$n$ (候选用例数，$1≤n≤10$ ) 接下来 $m$ 行依次为 $m$ 个接口信息：接口编号 $i$ ,接口重要度 $w_i$，接口耗时 $t_i$ 接下来 $n$ 行依次为 $n$ 个用例信息：用例编号 $j$ ，覆盖接口数 $l,c_1,c_2,…,c_ 2l$ 。其中 $c_1,c_2$ 为[接口编号 $i$ ,发现缺陷概率 p_i_j ]参数对，一共有 $l$ 组。

输出描述

最大“总测试收益"，如果无法满足约束，输出 $-1$

样例1

输入

10 3 2 2
1 4 3
2 2 2
1 2 1 0.04 2 0.78
2 2 1 0.17 2 0.63

输出

2.24

说明

总时长限制为 $10$ 、单个接口执行限制最多 $3$ 次、接口数 $2$、用例数 $2$

两个用例都选

时间消耗：用例 $1$ 时间 $5$ +用例 $2$ 时间 $5=10$，满足约束

执行次数：每个接口都是 $2$ 次，满足约束

接囗 $1$ 收益：$max(0.16,0.68)=0.68$

接囗 $2$ 收益：$max(1.56,1.26)=1.56$

总收益：$0.68+1.56=2.24$