前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Python|二分查找算法解决包裹最低运载问题

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

作者头像
算法与编程之美
修改2020-05-18 17:48:42
6440
修改2020-05-18 17:48:42
举报
文章被收录于专栏:算法与编程之美

问题描述

传送带上的包裹必须在 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,满足题意;

代码语言:javascript
复制
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 团队


本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2020-05-09,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 算法与编程之美 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档