现在有N个集装箱的货物要运走,你的任务是把这N箱的货物装到M艘船上。约束条件为: 1、集装箱是依次一箱一箱的送到码头,来到码头后必须立刻装到船上。船也是依次一艘一艘的来到码头,一艘船装完后立刻离开,然后才能装下一艘; 2、集装箱不能拆箱; 3、所有的船具有相同的载重量,假设为W,船上装的集装箱的总重量不能超过这个载重量; 你的任务是计算出W的最小值。 样例解释:第1艘船装(10,40)、第2艘船装(30,10)、第3艘船装(50)、第4艘船装(11)、第5艘船装(40)。这种情况下W为50,其他方式W均要大于50。 输入格式: 第一行为用空格分隔的2个整数,分别代表N和M。(1 <= N <= 100000 ,1 <= M <= N),接下来N行,每行为一个整数,依次(输入的顺序即是集装箱到达码头的顺序)代表每个集装箱的重量(该重量大于等于1且小于等于10000)。 输出格式: 只有一行,为一个整数,代表此条件下W的最小值。
时间: 2023-03-07 13:03:01 浏览: 133
装载问题有两艘船,载重量分别是c1、 c2,n个集装箱,重量是wi (i=1…n),且所有集装箱的总重量不超过c1+c2。确定是否有可能将所有集装箱全部装入两艘船
5星 · 资源好评率100%
我的答案是:根据给定的约束条件,W的最小值可以通过使用贪心算法来计算。首先,根据集装箱的重量和船只的数量,计算出每艘船的最大载重量;然后,从第一艘船开始,依次装载重量最大和最小的集装箱,直至每艘船装满,最后输出最后一艘船的最大载重量即可。
阅读全文