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

• 先頭の荷物がまだトラックの中に入る（トラックの中の荷物の重さの合計が \(M\) を越えない）なら、その荷物をトラックの中に入れる
• そうでなければ、今トラックの中にある荷物を運搬してから、先頭の荷物をトラックの中に入れる

荷物をうまく並べることで、この方法でトラックの台数を最小にすることができます。

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

\(\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],M\times\left\lceil\dfrac{\operatorname{dp}[S]}M\right\rceil+W _ i\right\rbrace\quad&((\operatorname{dp}[S]\bmod M)+W _ i\gt M)\\\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, M;
    cin >> N >> M;

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

    vector dp(1 << N, static_cast<long>(M) * 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] % M + W[i] > M) { // 入れると M を越えるなら
                    dp[S + (1 << i)] = min(dp[S + (1 << i)], (dp[S] + M - 1) / M * M + W[i]); // ダミーの荷物を詰めて送ってから荷物 i を入れる
                } else { // 越えないなら
                    dp[S + (1 << i)] = min(dp[S + (1 << i)], dp[S] + W[i]); // そのまま荷物 i を入れる
                }
            }
        }
    }

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

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

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

dp = [N * M 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] % M + W[i] > M: # 入れると M を越えるなら
                dp[S + (1 << i)] = min(dp[S + (1 << i)], (dp[S] + M - 1) // M * M + W[i]) # ダミーの荷物を詰めて送ってから荷物 i を入れる
            else: # そうでなければ
                dp[S + (1 << i)] = min(dp[S + (1 << i)], dp[S] + W[i]); # そのまま荷物 i を入れる

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