同和新媒体矩阵官网同和视频矩阵同和素材矩阵

登录 | 立即注册

同和创作矩阵 › ›博文归档› 技术博文归档 › 查看内容

2093_AL101太空飞行计划问题

2022-5-16 18:18| 发布者: Hocassian| 查看: 23| 评论: 0|原作者: 肇庆学院ACM合集

摘要:

C:\Users\Administrator\Downloads\2019-10-12-10-14-3-89504319300800-Problem List-采集的数据-后羿采集器.html

Pro.ID

2093

Title

AL101 太空飞行计划问题

Title链接

http://10.20.2.8/oj/exercise/problem?problem_id=2093

AC

0

Submit

28

Ratio

0.00%

时间&空间限制

Time Limit: 1200/400 MS (Java/Others) Memory Limit: 131072/65536 K (Java/Others)

描述

W 教授正在为国家航天中心计划一系列的太空飞行。每次太空飞行可进行一系列商业性实验而获取利润。现已确定了一个可供选择的实验集合E={E₁，E₂，…，E_m}，和进行这些实验需要使用的全部仪器的集合I={I₁，I₂，…I_n}。实验Ej需要用到的仪器是I的子集R_jI。配置仪器I_k的费用为c_k美元。实验E_j的赞助商已同意为该实验结果支付p_j美元。W教授的任务是找出一个有效算法，确定在一次太空飞行中要进行哪些实验并因此而配置哪些仪器才能使太空飞行的净收益最大。这里净收益是指进行实验所获得的全部收入与配置仪器的全部费用的差额。

对于给定的实验和仪器配置情况，编程找出净收益最大的试验计划。

输入

输入第一行是两个正整数m和n。m是实验数，n是仪器数。接下来的m 行，每行是一个实验的有关数据。第一个数赞助商同意支付该实验的费用；接着是该实验需要用到的若干仪器的编号。最后一行的n个数是配置每个仪器的费用。

0 < m, n < 50

输出

Description

W 教授正在为国家航天中心计划一系列的太空飞行。每次太空飞行可进行一系列商业性实验而获取利润。现已确定了一个可供选择的实验集合E={E₁，E₂，…，E_m}，和进行这些实验需要使用的全部仪器的集合I={I₁，I₂，…I_n}。实验Ej需要用到的仪器是I的子集R_jI。配置仪器I_k的费用为c_k美元。实验E_j的赞助商已同意为该实验结果支付p_j美元。W教授的任务是找出一个有效算法，确定在一次太空飞行中要进行哪些实验并因此而配置哪些仪器才能使太空飞行的净收益最大。这里净收益是指进行实验所获得的全部收入与配置仪器的全部费用的差额。

对于给定的实验和仪器配置情况，编程找出净收益最大的试验计划。

Input

输入第一行是两个正整数m和n。m是实验数，n是仪器数。接下来的m 行，每行是一个实验的有关数据。第一个数赞助商同意支付该实验的费用；接着是该实验需要用到的若干仪器的编号。最后一行的n个数是配置每个仪器的费用。

0 < m, n < 50

Output

输出最佳实验方案：第一行是实验编号；第二行是仪器编号；最后一行是净收益。

Sample Input

2 3
10 1 2
25 2 3
5 6 7

Sample Output

1 2
1 2 3
17

Author

样例输入

2 3
10 1 2
25 2 3
5 6 7

样例输出

1 2
1 2 3
17

提示

作者

最新评论

相关分类

返回顶部