货轮问题货轮公司的每一条货轮都有最大载柜量和最大载重吨位约束。正常情况下货轮公司会约定集装箱限重以集装箱个数向客户收费。现在货轮公司希望最大化利润采用货柜提前预定制度。 该预定制度规定如下货轮公司邀请客户提交集装箱可能的重量与运费报价然后货轮公司承诺运载一部分客户的集装箱并告知其优先级顺序。实际承运时货物按照优先级顺序运上船若没有超过货轮最大载柜量和最大载重吨位约束则收取客户运费报价;若超过货轮约

对于一号货轮，我们可以使用贪心算法来选择客户。首先，按照报价从高到低排序，然后依次考虑每个客户。对于每个客户，我们枚举其集装箱可能的重量，并计算加上该集装箱后是否超过了货轮的约束条件。如果没有超过，就将该客户加入承运列表，并将该集装箱加入货轮。如果超过了，就跳过该客户。最终得到的承运列表即为最优解。在本例中，最终承运的客户为1、5和3，承运的集装箱重量分别为5、6和4，总收益为27。这是最优解，因为所有客户的报价都被考虑到了，且没有超过货轮的约束条件。

对于二号货轮，由于客户数量较多，我们可以使用动态规划来解决。我们定义状态f(i,j,k)表示前i个客户中选择了j个集装箱，重量不超过k的最大收益。转移方程为f(i,j,k)=max(f(i-1,j,k),f(i-1,j-1,k-w)+p)，其中w和p分别表示第i个客户选择的集装箱重量和报价。最终的最大收益即为f(30,30,300)。由于状态数较多，需要使用记忆化搜索或者自底向上的方式进行动态规划。在本例中，最终的最大收益为1346.5，承运的客户和集装箱重量见附件二。

对于三号货轮，我们可以先计算每个客户选择每个集装箱重量的期望收益，然后按照期望收益从高到低排序。依次考虑每个客户，如果加上其选择的集装箱后不超过货轮的约束条件，则将该客户加入承运列表，并将该集装箱加入货轮。如果超过了，则跳过该客户。最终得到的承运列表即为最优解。在本例中，最终承运的客户为1和4，承运的集装箱重量分别为4.5和6，总收益为9。这是最优解，因为所有客户的报价和期望收益都被考虑到了，且没有超过货轮的约束条件。预期收益为9，因为所有客户的报价都被考虑到了，且没有需要赔付10倍运费报价的情况