HBC213816二分图染色,动态规划,组合数学,排列组合[网络流24题]太空飞行计划问题题解

庄子墨算法基础篇 2023-11-23 23:38:02 56 0

挑战自我，勇攀编程高峰！全网最全C++题库，助您成为编程达人。

美元，实验Ej的赞助商已同意为该实验结果支付pj美元，W教授的任务是找出一个有效算法，确定在一次太空飞行中要进行哪些实验并因此而配置哪些仪器才能使太空飞行的净收益最大，这里净收益是指进行实验所获得的全部收入与配置仪器的全部费用的差额。

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