公式

E - エレベーターの運搬 / Elevator Transport 解説 by MMNMM

荷物を運んでいる途中（いくつかの荷物を目的階まで運んだ時点で）、「次に運ぶことができる荷物のグループとしてありえるもの」や「その中で運搬回数が最小となるもの」は、これまでに運んだ荷物の集合によってのみ決まります（運んだ順番や、これまでの運搬回数には影響されません）。 よって、「これまでに運んだ荷物の集合」を状態に持つ動的計画法によってこの問題を解くことを考えます。

以下のような DP を考えます。

  • \(\operatorname{dp}[S]\coloneqq{}\)これまでに運んだ荷物の集合が \(S\) であるような運び方における、これまでの運搬回数としてありえる最小値 \(\ (S\subseteq\lbrace1,2,\ldots,N\rbrace)\)

これを使えば、適切な順番（例えば \(S\) に含まれる要素数の昇順など）で次のような更新を行うことでこの問題を解くことができます。

  • \(\operatorname{dp}[S\cup T]\leftarrow\min\lbrace\operatorname{dp}[S\cup T],\operatorname{dp}[S]+1\rbrace\ (S\cap T=\emptyset,T\) に含まれる荷物の重さの合計は \(C\) 以下\()\)

それぞれの \(S\) に対して、DP の更新は \(\bigl(\ T\) としてありえる個数 \(\bigr)\) 回行われます。 全体で \(\displaystyle\sum _ {S\subseteq\lbrace1,2,\ldots,N\rbrace}\sum _ {S\cap T=\emptyset,T\subseteq\lbrace1,2,\ldots,N\rbrace}1\) 回となり、これは \(3 ^ N\) になります（\(N\) 個の要素を「\(S\) に含まれるもの」「\(T\) に含まれるもの」「どちらにも含まれないもの」の \(3\) つに分ける場合の数と考えることができます）。

\(S\) についてのループを回し、\(T\) に含まれる荷物の重さの合計を毎回求めると時間計算量は \(O(N3 ^ N)\) となります。 この方針でも、高速な言語を用いて実装すれば実行時間制限に間に合う場合があります。

実装例は以下のようになります。 筆者はこの方針で Python を実行時間制限に間に合わせることはできませんでした。

実装例

#include <iostream>
#include <vector>
using namespace std;

int main(){
    int N, C;
    cin >> N >> C;

    vector<int> W(N);
    for (int& w : W) {
        cin >> w;
    }

    auto check_weight = [&](int T) { // T に含まれる荷物の重さの合計が C 以下か判定する
        int sum = 0;
        for (int i = 0; i < N; ++i) {
            if (1 & (T >> i)) {
                sum += W[i];
                if (sum > C) {
                    return false;
                }
            }
        }
        return true;
    };

    vector dp(1 << N, N); // 必ず N 回以内で運べるので、N で初期化しておく
    dp[0] = 0;

    for (int S = 0; S < 1 << N; ++S) {
        for (int T = 0; T < 1 << N; T = T + S + 1 & ~S) { // S と共通部分をもたない T について
            if (check_weight(T)) { // 合計が C 以下なら
                dp[S | T] = min(dp[S | T], dp[S] + 1); // DP を更新
            }
        }
    }

    cout << dp.back() << endl; // 全部運びきるのにかかる回数を出力
    return 0;
}

N, C = map(int, input().split())

W = list(map(int, input().split()))

def check_weight(T): # T に含まれる荷物の重さの合計が C 以下か判定する
    return sum(W[i] for i in range(N) if 1 & (T >> i)) <= C

dp = [N for _ in range(1 << N)] # 必ず N 回以内で運べるので、N で初期化しておく
dp[0] = 0

for S in range(1 << N):
    T = 0
    while T < (1 << N):
        if check_weight(T): # 合計が C 以下なら
            dp[S + T] = min(dp[S + T], dp[S] + 1) # DP を更新
        T = (T + S + 1) & ~S # S と共通部分をもたない T を列挙する

print(dp[-1]) # 全部運びきるのにかかる回数を出力

時間計算量を削減するひとつの方法は、\(S\) でまずループを回すのではなく、\(T\) のループを外側にすることです。 \(T\) のループで重さの合計の判定を行ってから内部の処理を行うことができるため、時間計算量は \(O(3 ^ N)\) になります。

実装例は以下のようになります。

実装例

#include <iostream>
#include <vector>
using namespace std;

int main(){
    int N, C;
    cin >> N >> C;

    vector<int> W(N);
    for (int& w : W) {
        cin >> w;
    }

    auto check_weight = [&](int T) { // T に含まれる荷物の重さの合計が C 以下か判定する
        int sum = 0;
        for (int i = 0; i < N; ++i) {
            if (1 & (T >> i)) {
                sum += W[i];
                if (sum > C) {
                    return false;
                }
            }
        }
        return true;
    };

    vector dp(1 << N, N); // 必ず N 回以内で運べるので、N で初期化しておく
    dp[0] = 0;

    for (int T = 0; T < 1 << N; ++T) {
        if (check_weight(T)) { // 合計が C 以下なら
            for (int S = 0; S < 1 << N; S = S + T + 1 & ~T) { // T と共通部分をもたない S について
                dp[S | T] = min(dp[S | T], dp[S] + 1); // DP を更新
            }
        }
    }

    cout << dp.back() << endl; // 全部運びきるのにかかる回数を出力
    return 0;
}

N, C = map(int, input().split())

W = list(map(int, input().split()))

def check_weight(T): # T に含まれる荷物の重さの合計が C 以下か判定する
    return sum(W[i] for i in range(N) if 1 & (T >> i)) <= C

dp = [N for _ in range(1 << N)] # 必ず N 回以内で運べるので、N で初期化しておく
dp[0] = 0

for T in range(1 << N):
    if check_weight(T): # 合計が C 以下なら
        S = 0
        while S < (1 << N):
            dp[S + T] = min(dp[S + T], dp[S] + 1) # DP を更新
            S = (S + T + 1) & ~T # T と共通部分をもたない S を列挙する

print(dp[-1]) # 全部運びきるのにかかる回数を出力

少し違う方針の解法も説明します。

荷物を一列に並べ、次のように運んでいくことを考えます。

  • 先頭の荷物がまだエレベーターの中に入る（エレベーターの中の荷物の重さの合計が \(C\) を越えない）なら、その荷物をエレベーターの中に入れる
  • そうでなければ、今エレベーターの中にある荷物を運搬してから、先頭の荷物をエレベーターの中に入れる

荷物をうまく並べることで、この方法で運搬回数を最小にすることができます。

また、エレベーターの中にある荷物を運搬する際に、ダミーの荷物を使って運搬する重さを毎回 \(C\) に揃えることにすると、「これまでエレベーターの中に入れた荷物の重さの合計」で並べ方を順序付けることができます。

\(\operatorname{dp}[S]\coloneqq\) これまでにエレベーターの中に入れた荷物の集合が \(S\) のときの、これまでにエレベーターの中に入れた（ダミーの荷物も含む）荷物の重さの合計としてありえる最小値 \(\ (S\subseteq\lbrace1,2,\ldots,N\rbrace)\)と定めると、適切な順番で次のような更新を行うことでこの問題を解くことができます。

  • \(\operatorname{dp}[S\cup\lbrace i\rbrace]\leftarrow\begin{cases}\min\left\lbrace \operatorname{dp}[S\cup\lbrace i\rbrace],C\times\left\lceil\dfrac{\operatorname{dp}[S]}C\right\rceil+W _ i\right\rbrace\quad&((\operatorname{dp}[S]\bmod C)+W _ i\gt C)\\\min\left\lbrace \operatorname{dp}[S\cup\lbrace i\rbrace],\operatorname{dp}[S]+W _ i\right\rbrace&(\text{otherwise})\end{cases}\)

これは \(O(N2 ^ N)\) 時間で計算することができ、十分高速です。

実装例は以下のようになります。

実装例

#include <iostream>
#include <vector>
using namespace std;

int main(){
    int N, C;
    cin >> N >> C;

    vector<int> W(N);
    for (int& w : W) {
        cin >> w;
    }

    vector dp(1 << N, static_cast<long>(C) * N);
    dp[0] = 0;

    for (int S = 0; S < 1 << N; ++S) {
        for (int i = 0; i < N; ++i) {
            if (!(1 & (S >> i))) { // まだ運んでいない荷物について
                if (dp[S] % C + W[i] > C) { // 入れると C を越えるなら
                    dp[S + (1 << i)] = min(dp[S + (1 << i)], (dp[S] + C - 1) / C * C + W[i]); // ダミーの荷物を詰めて送ってから荷物 i を入れる
                } else { // 越えないなら
                    dp[S + (1 << i)] = min(dp[S + (1 << i)], dp[S] + W[i]); // そのまま荷物 i を入れる
                }
            }
        }
    }

    cout << (dp.back() + C - 1) / C << endl; // 全部運びきるのにかかる回数を出力
    return 0;
}

N, C = map(int, input().split())

W = list(map(int, input().split()))

dp = [N * C for _ in range(1 << N)]
dp[0] = 0

for S in range(1 << N):
    for i in range(N):
        if not 1 & (S >> i): # まだ運んでいない荷物について
            if dp[S] % C + W[i] > C: # 入れると C を越えるなら
                dp[S + (1 << i)] = min(dp[S + (1 << i)], (dp[S] + C - 1) // C * C + W[i]) # ダミーの荷物を詰めて送ってから荷物 i を入れる
            else: # そうでなければ
                dp[S + (1 << i)] = min(dp[S + (1 << i)], dp[S] + W[i]); # そのまま荷物 i を入れる

print((dp[-1] + C - 1) // C) # 全部運びきるのにかかる回数を出力

投稿日時:
最終更新: