Python|二分查找算法解决包裹最低运载问题

问题描述

传送带上的包裹必须在 D 天内从一个港口运送到另一个港口。传送带上的第i个包裹的重量为 weights[i]。每一天，都会按给出重量的顺序往传送带上装载包裹。装载的重量不会超过船的最大运载重量。返回能在 D 天内将传送带上的所有包裹送达的船的最低运载能力。

示例 1：

输入：weights = [1,2,3,4,5,6,7,8,9,10], D = 5

输出：15

解释：船舶最低载重 15 就能够在 5 天内送达所有包裹，如下所示：

第 1 天：1, 2, 3, 4, 5

第 2 天：6, 7

第 3 天：8

第 4 天：9

第 5 天：10

请注意，货物必须按照给定的顺序装运，因此使用载重能力为 14 的船舶并将包装分成 (2, 3, 4, 5), (1, 6, 7), (8), (9), (10) 是不允许的。

示例 2：

输入：weights = [3,2,2,4,1,4], D = 3

输出：6

解释：

船舶最低载重 6 就能够在 3 天内送达所有包裹，如下所示：

第 1 天：3, 2

第 2 天：2, 4

第 3 天：1, 4

示例 3：

输入：weights = [1,2,3,1,1], D = 4

输出：3

解释：

第 1 天：1

第 2 天：2

第 3 天：3

第 4 天：1, 1

解决方案

如果采用暴力法去取每一个值，并判断是否符合题意，这时会发现，如果weights的值有很多个时，会出现超时的情况，这时就会用到二分查找算法来降低算法时间复杂度。

二分查找算法：

a为取值的下限，b为取值的上限，tar为当前取值

判断tar过大还是过小，如果tar过大那么，上限b缩短为tar，tar变为(tar+a)/2；

同理，过小下限a就变为tar，tar变为(tar+b)/2；

一直持续下去，直到满足题意所给出的条件即可。

代码解决及解析

1.定义一个jg函数用来处理所需的运载天数，其中tar为运载的能力(即题目中的最大运载量)，s用来记录当前的重量，day用来记载所用天数；即得到运载能力(tar)所对应的运载天数(day)；

2.创建一个a,b分别表示运载能力的上下限，a表示下限，b表示上限，因为下限a的最小值一定是=max(weights)，这样才能保证weights中的每个值都能运载，不会超载；同理当运载能力上限b=sum(weights)时，只需1天就能运载完毕；故得出载重上下限a,b;

3.其次，定一个res数组用来装入运载能力(tar)所对应的运载天数(day)<D时的tar值,即满足题意的tar值，tar为二分查找的中值，即(a+b)/2，即上下限值和的一半，当然在每个判断条件之后，会采用二分法来改变上下限的值。(注意：该题中的tar值类型为float,故在加入res中时应该是int(tar),判断时，也应该转化为int类型)

4.加入res的值为day<=D时的int(tar)值,因为此时的tar所对应的day<=D，满足题意；

class Solution:

    def shipWithinDays(self, weights: List[int], D: int) -> int:

        def jg(weights,tar):#tar为运载能力

            s,day=0,0

            for i in weights:#遍历weights的每天重量

                if s+i>tar:#当前的重量 + 当该天的包裹重量 > 当前最大运载能力tar；当天包裹重量就一起不能运载，会超重

                    day,s=day+1,i #天数+1，s当前重量就变为该天的包裹重量

                else:#反之，当前重量+该天包裹重量

                    s+=i

            return day+1

        a,b=max(weights),sum(weights)#a表示运载能力下限，b表示运载能力上限

        if len(weights)<D:#如果运载天数大于包裹的个数，直接返回下限,因为就算每天只运一个包裹也不会超过D,故返回下限即可；

            return a

        res,tar=[],(a+b)/2

        while int(tar) not in res:#当tar存在于res中时终止循环

            day=jg(weights,tar)

            if day<D:#运载能力(tar)所对应的运载天数(day)<D时，表示运载能力过大故采用二分法，上限b应该缩短到tar，tar应该变为当前(tar+a)/2(代码中b=tar，故采用的b代替tar)，后者day>D同理。

                res.append(int(tar))

                b=tar

                tar=(a+b)/2

            elif day==D:#如果运载能力(tar)所对应的运载天数(day)=D时，表示运载能力所对应的天数不能再减少了，此时，就需要(运载能力(tar)-1)来逐步逼近所取满足条件的tar的最小值；

                res.append(int(tar))

                tar=tar-1

            else:

                a=tar

                tar=(b+a)/2

        return max(min(res),max(weights))

结语

该博客主要讲解了如何用二分法思考并解决包裹最低运载问题，当然该题以及二分查找算法的最重要的还是取值(tar)上下限的变化，与暴力法相比，二分查找算法来求解，极大的减少了搜索的范围，从而降低了算法时间复杂度。

END

主 编 | 王文星

责 编 | 王卓越

where2go 团队