Knapsack Problem (Meet in the middle)

概要

以下のような問題

  • \(N\) 種類の品物がある

  • \(i\) 番目の品物の価値は \(v_i\), 容量は \(w_i\)

  • 重さの総和 \(W\) まで入るナップサックに入れる

  • ナップサックに入る品物の価値を最大化する

  • 制約の一例は以下

  • \(1 \le N \le 40\)

  • \(1 \le W \le 10^{15}\)

  • \(1 \le v_i \le 10^{15}\)

  • \(1 \le w_i \le 10^{15}\)

\(N\) が小さいため、半分全列挙で解く問題。

品物を半分に分けて全列挙(\(O(2^{N/2})\))した上で、 ２つの集合について、一方は小さい方からでもう一方は大きい方から、 重さが \(W\) 以下になるようにスライドさせながら価値の最大値を求める。

計算量

\(O(2^{N/2})\)

実装

# i番目の重みws[i], 価値vs[i]
def solve(N, W, ws, vs):
    # S[i] = (v, w): 価値v, 重さw
    *S, = zip(vs, ws)

    def make(S):
        T = {0: 0}
        for v, w in S:
            # 価値v, 重さw
            T0 = dict(T)
            for k, val in T.items():
                if k+w > W:
                    continue
                if k+w in T0:
                    T0[k+w] = max(T0[k+w], val + v)
                else:
                    T0[k+w] = val + v
            T = T0
        v = 0
        R = []
        for k in sorted(T):
            v = max(v, T[k])
            # (重さk, 重さk以下での価値の最大v)
            R.append((k, v))
        return R

    def solve(T0, T1):
        T0.sort()
        T1.sort(reverse=1)

        it = iter(T1); k1, v1 = next(it)
        yield 0
        for k0, v0 in T0:
            # 重さの和がW以下になるようにスライドする
            while k0 + k1 > W:
                k1, v1 = next(it)
            yield v0 + v1

    # ２つの集合に分けて、それぞれ全列挙
    T0 = make(S[:N//2])
    T1 = make(S[N//2:])

    # 2つの全列挙を元に解を求める
    return max(solve(T0, T1))

Verified

  • AOJ: "DPL_1_H: Combinatorial - Huge Knapsack Problem": source (Python3, 4.32sec)

戻る