W 教授正在为国家航天中心计划一系列的太空飞行。每次太空飞行可进行一系列商业性实验而获取利润。现已确定了一个可供选择的实验集合 E={E1,E2,⋯,Em} E = \{ E_1, E_2, \cdots, E_m \} E={E1,E2,⋯,Em},和进行这些实验需要使用的全部仪器的集合 I={I1,I2,⋯,In} I = \{ I_1, I_2, \cdots, I_n \} I={I1,I2,⋯,In}。实验 Ej E_j Ej 需要用到的仪器是 I I I 的子集 Rj⊆I R_j \subseteq I Rj⊆I。
配置仪器 Ik I_k Ik 的费用为 ck c_k ck 美元。实验 Ej E_j Ej 的赞助商已同意为该实验结果支付 pj p_j pj 美元。W 教授的任务是找出一个有效算法,确定在一次太空飞行中要进行哪些实验并因此而配置哪些仪器才能使太空飞行的净收益最大。这里净收益是指进行实验所获得的全部收入与配置仪器的全部费用的差额。
对于给定的实验和仪器配置情况,编程找出净收益最大的试验计划。