什么样的算法？(背包,装箱!？)

Question

问题如下:

您有n个行程长度(以km为单位),应在m天之间进行划分,以使每天最大长度总和最小化.例如,在3天内划分的行程长度[1,5,2,6,8,3,2]导致[1,5,2] [6] [8,3,2]因为最大日长度总和是我们能达到的最低点.

是否有一种描述处理这种问题的算法？我遇到了bin包装和背包问题,但没有一个能解决我的问题.我可以想象它可能是对bin包装的一点修改但是没有得出结论.

Answer 1

这个问题可以用二分查找来解决

假设最大长度为，我们可以通过以下贪婪方法X轻松检查是否可以将行程分为 m 天，并且每天的最大长度不大于：X

boolean isValid(int X){
   int currentLength = 0;
   int numberOfDays = 1;
   for(int i = 0; i < n; i++)
      if (trip[i] > X)
         return false;
      if(currentLength + trip[i] <= X){
         currentLength += trip[i];  
      }else{
         currentLength = trip[i];
         numberOfDays++;
      }
   }
   return numberOfDays <= m;
}

然后，我们可以通过以下二分查找轻松找到 X 的最小值：

int start = 0;
int end = sum of all trips;
int result = end;
while(start <=end){
    int mid = (start + end)/2;
    if(isValid(mid)){
       result = mid;
       end = mid - 1;
    }else{
       start = mid + 1;
    }
}

时间复杂度为O(n log z)，其中z是所有行程的总和。