1412-太空实验计划


    内存限制:64MB 时间限制:1000ms 特判: No

    通过数:1 提交数:5 难度:6


题目描述:

某理工学院的实验室计划了一系列的实验项目E{E1E2…,Em},这些实验需要使用的全部仪器集合I{I1I2…,In}。每个实验需要的仪器是全部仪器集合的子集。配置仪器Ij需要的费用为cj,实验Ei产生的经济效益为pi美元。需要设计一个有效的算法,确定要进行哪些实验,使最终得到的经济效益减去需要配置的仪器费用后得到的净收益最大。


输入描述:

第一行是一个整型数C(C<100)表示共有C组测试数据。
每组测试数据第一行输入实验数m和仪器数n(1<=m,n<=100)。
接下来m行,输入实验产生的效益w和该实验需要的仪器编号ci(为0结束)。(1<=w<=100,1<=ci<=n)。
最后一行n个数,输入所有仪器的费用cost(1<=cost<=100)。

输出描述:

对于每一组输入,输出最大净收益。
每组的输出占1行。

样例输入:

1
5 15
20 2 4 8 11 0
38 1 5 14 0
25 2 5 7 15 0
17 1 3 6 9 13 0
22 10 12 15 0
2 7 4 8 10 1 3 7 5 9 15 6 12 17 8

样例输出:

23

提示:


上传者:rainflychxy

书中题目链接,请点击上面链接访问!

公告

    欢迎使用NYOJ2.0!