読者です 読者をやめる 読者になる 読者になる

yukicoder No.50 おもちゃ箱

問題

★★★

No.50 おもちゃ箱 - yukicoder

考察

おもちゃ・箱の数は少なく、大きさの最大値も小さいです。
ただ、2つのバラバラな数列があるため、単純に手前からとはいきません。
そこで、箱を順番に処理し、「その箱の中でどれだけ使っているか」「どのおもちゃを取ったか」という情報を使ってDPします。

dp[i][j][S] := i番目の箱がjだけ埋まっていてSのおもちゃを取っている時の、使用した最小の箱の数

「どのおもちゃを取ったか」という集合は、おもちゃを取るごとにビットが立ってゆくので、0(何も取っていない)からループすることで正しい順序で処理ができます。

各DPの要素では、「次にどのおもちゃを取るか」を決めます。
そのため、計算量は全体で O(M * max(B) * 2^{N} * N)です。

「箱に入れるだけ」「箱に入れて次の箱へ」「入れずに次の箱へ」という3種類を処理すると、もれなく埋めることができます。

答えは、「最後の箱まで見て」「全部のおもちゃを取った」状態の中で最小になる値です。

コード

int main() {
    int N;
    cin >> N;
    vi A(N);
    rep(i, N)cin >> A[i];
    int M;
    cin >> M;
    vi B(M);
    rep(i, M)cin >> B[i];

    const int NPOW = 1 << N;

    vvvi dp(M + 1, vvi(21, vi(NPOW, INF)));
    dp[0][0][0] = 0;

    rep(i, M) {
        rep(j, 21) {
            rep(S, NPOW) {
                if (dp[i][j][S] == INF)
                    continue;
                rep(k, N) {
                    // まだ入れていない
                    if (((S >> k) & 1) == 0) {
                        if (A[k] <= B[i] - j) {
                            // 入れてそのまま
                            chmin(dp[i][j + A[k]][S | (1 << k)], dp[i][j][S]);
                            // 入れて次へ
                            chmin(dp[i + 1][0][S | (1 << k)], dp[i][j][S] + 1);
                        }
                    }
                }
                // 次のハコへ
                chmin(dp[i + 1][0][S], dp[i][j][S] + (j > 0));
            }
        }
    }

    int ans = INF;
    rep(j, 21) {
        chmin(ans, dp[M][j][NPOW - 1]);
    }
    if (ans != INF)
        cout << ans << endl;
    else
        cout << -1 << endl;


    return 0;
}

備考

↑のようなややこしいDPをしましたが、大きい順に使えば良いので、最初にソートすると簡単高速になります。
詳細は、↓の素晴らしい解説をご覧ください。

yukicoder No.50 - おもちゃ箱 - ゲームにっき(仮)別館(仮)