実装して学ぶ基本探索アルゴリズム ~二分探索の応用~

解答部分だけに興味がある方は二分探索による実装からみてください

目次

基本探索アルゴリズムの応用問題

今回扱うのはALDS1_4_D:Allocationです．
最大積載量が決まっているトラックに対して荷物をどう割り当てるかというのがこの問題の趣旨になります．
詳しく問題文を読み解いていきます．.
重さがそれぞれw_i(i = 0, 1,…, n-1)のn個の荷物をk台のトラックに積みます．トラックには荷物はいくらでも載せられますが，最大積載量Pを超えられません．この時の最大積載量Pの最小値を求めるという問題になります．
制約は

• 1 ≦ n ≦ 100000
• 1 ≦ k ≦ 100000
• 1 ≦ w ≦ 10000

となっています．

線形探索による実装

まず，問題を解く時に考えられるのが線形探索の考え方を使い，最大積載量Pを0から増やしていき，その時に荷物を積み切ることができるかどうか調べていくということが考えられます．
では，線形探索を用いて実装していきます．

#Pの時に必要なトラックの数を求める関数
def unit_check(n, k, w_list, P):
    i = 0
    for j in range(k):
        weight = 0
        while weight + w_list[i] <= P:
            weight += w_list[i]
            i += 1
            if i == n:
                return 1
    return 0

n, k = map(int,input().split())
w_list = [0] * n
for i in range(n):
    w_list[i] = int(input())

P = max(w_list) - 1
flag = 0
while flag == 0:
    P += 1
    flag = unit_check(n,k,w_list,P)
print(P)

このコードの提出結果は次のようになります．

二分探索による実装

前述のコードの結果を見ると問題自体は解けているようですが，計算時間が間に合わないことがわかります．
ここで注目して欲しいところが，Pの値を一つずつ増やしているという部分です．
基本的には P で積載できなければ P+1 でも積載できない可能性が高いので，Pの値を大きく動かしながら探索した方が検討をつけやすいことがわかると思います．
そこで，これまでに学んだ二分探索を使ってPの値を作成する部分を調整してみましょう．
では，早速実装していきます．

#Pの時に必要なトラックの数を求める関数
def unit_check(n, k, w_list, P):
    i = 0
    for j in range(k):
        weight = 0
        while weight + w_list[i] <= P:
            weight += w_list[i]
            i += 1
            if i == n:
                return 1
    return 0

n, k = map(int,input().split())
w_list = [0] * n
for i in range(n):
    w_list[i] = int(input())

left = 0
#荷物の最大数x荷物の最大の重さ
right = 100000*10000
while left+1 < right:
    mid = (left+ right)//2
    check = unit_check(n, k, w_list, mid)
    if check == 1:
        right = mid
    else:
        left = mid
print(right)

このコードでの提出結果

コード解説

まず，rightの初期値ですが，荷物の最大数x荷物の最大の重さとすることで k=1 の時でもトラックに全ての荷物を積むことができるので，このような値を取っています．
"while left + 1< right" の部分に関しては今回はleftとrightが共存するということがなく,"while left < right"とするとループを抜けられなくなってしまうのでこのようになっています．
最後にrightを出力しているのはunit_checkで"1"が帰ってきている中で最小のものが答えなのでwhileを抜けた時のrightが答えになっています．

コードの中身に関してこうした方がいいやここがわからないなどあればコメントよろしくお願いします！