[Aizu Online Judge] 二分法を利用した最適解の計算 (ALDS1_4_D: Allocation)

二分法

二分探索はソート済の配列を探索するアルゴリズムとして有名ですが、数値計算で二分法というものがあります。

二分法は、解の範囲が既知のとき、範囲の中間値を解の候補として探索していく手法です。

高校数学まででは馴染みがないですが、入試でみかけるニュートン法の問題を解いたことがあるので、イメージはつきました。

ALDS1_4_D: Allocation

割り当て | アルゴリズムとデータ構造 | Aizu Online Judge

この問題の肝は、最大積載量 の候補をどのようにして決めるかということです。

の最大値は、荷物の最大重量×荷物の最大個数です。最小値は、荷物の最大重量です。

しかし、入力される値はソートされていないので、 の最大値を制約の最大を取ると考えます。また、最小値は として差し支えないです。

したがって、解の範囲が分かったので、この範囲を二分法を用いて解きます。

コード

import java.util.Scanner;

public class ALDS1_4_D {
    public static int n;
    public static int k;
    public static int []w;
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        k = scan.nextInt();
        w = new int[n];
        for(int i = 0; i < n; i++) {
            w[i] = scan.nextInt();
        }
        scan.close();
        long ans = solve();
        System.out.println(ans);
    }
    public static int check(long p) {
        int i = 0;
        for(int j = 0; j < k; j++) {
            long s = 0;
            while(s + w[i] <= p) {
                s += w[i];
                i++;
                if(i == n) return n;
            }
        }
        return i;
    }
    public static long solve() {
        long left = 0;
        // 荷物の個数×1個当たりの最大重量
        long right = 100000 * 10000;
        long mid;
        while(right - left > 1) {
            mid = (left + right) / 2;
            int v = check(mid);
            if(v >= n) right = mid;
            else left = mid;
        }
        return right;
    }
}