Knapsack Problem

概要

以下のような問題

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

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

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

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

0-1ナップサック問題: \(O(N^2 \max_i{v_i})\)

制約の一例は以下

  • \(1 \le N \le 100\)

  • \(1 \le W \le 10^9\)

  • \(1 \le v_i \le 100\)

  • \(1 \le w_i \le 10^9\)

  • \(c_i = 1\)

各価値\(v (\le \sum_i v_i)\)の最小の重みを求める

# i番目の重みws[i], 価値vs[i]
def solve(N, W, ws, vs):
    # V = 全ての品物の価値の総和
    V = sum(vs)

    # 初期値は価値0以外の重さを上限より大きく
    dp = [W+1] * (V + 1)
    dp[0] = 0
    for i in range(N):
        # 価値v, 重さw
        v = vs[i]; w = ws[i]
        for j in range(V, v-1, -1):
            dp[j] = min(dp[j-v] + w, dp[j])

    # 重さが上限以下の価値のうち、最大の価値が解
    return max(i for i in range(V+1) if dp[i] <= W)

Verified

  • AOJ: "DPL_1_F: Combinatorial - 0-1 Knapsack Problem II": source (Python3, 0.58sec)

個数制限付きナップサック問題: \(O(N^2 \max_i{v_i} \max_i{c_i})\)

制約の一例は以下

  • \(1 \le N \le 50\)

  • \(1 \le W \le 10^9\)

  • \(1 \le v_i \le 50\)

  • \(1 \le w_i \le 10^9\)

  • \(1 \le c_i \le 50\)

dequeを用いたSliding Window Minimumを利用する

各価値\(v (\le \sum_i v_i \cdot c_i)\)の最小の重みを求める

from collections import deque

# i番目の重みws[i], 価値vs[i], 個数ms[i]
def solve(N, W, vs, ws, ms):
    V = sum(v * m for v, m in zip(vs, ms))

    # Sliding Window Minimum を用いたdpを行う
    dp = [W+1]*(V + 1)
    dp[0] = 0
    for i in range(N):
        # 価値v, 重さw, 個数m
        v = vs[i]; w = ws[i]; m = ms[i]
        c = m
        ms[i] -= c
        for k in range(v):
            que = deque()
            push = que.append
            popf = que.popleft; popb = que.pop

            for j in range((V-k)//v+1):
                a = dp[k + j*v] - j * w
                while que and a <= que[-1][1]:
                    popb()
                push((j, a))

                p, b = que[0]

                dp[k + j*v] = b + j * w
                if que and p <= j-c:
                    popf()
    return max(i for i in range(V+1) if dp[i] <= W)

個数制限付きナップサック問題: \(O(N^2 \max_i{v_i}^2)\)

制約の一例は以下

  • \(1 \le N \le 50\)

  • \(1 \le W \le 10^9\)

  • \(1 \le v_i \le 50\)

  • \(1 \le w_i \le 10^9\)

  • \(1 \le c_i \le 10^9\)

  1. 各品物 \(m_i = \min(\max_j v_j, c_i)\) 個に絞った個数制限付きナップサック問題を解く

    • 各価値\(v (\le \sum_i v_i \cdot m_i)\)の最小の重みを求める

    • dequeを用いたSliding Window Minimumを利用

    • これらの最小重みを求めるのに全体で \(O(N^2 \max_i{v_i}^2)\)

  2. (1)で求めた各価値\(v\)とその最小の重み\(w\)に対し、\(W - w\)の容量に品物を貪欲に詰めていく

    • \(\frac{v_i}{w_i}\) (つまり、重み単位に対する価値) が大きい品物から最大\((c_i - m_i)\)個を順番に詰める

    • 貪欲に詰めれた商品の価値の総和 + 価値v が1つの解 (各価値ごとに \(O(N)\))

    • 各\((v, w)\) に対しこれを求め、価値の最大を求める

    • 全ての価値\(v\)に対する計算量は \(O(N^2 \max_i{v_i}^2)\)

全体の計算量は \(O(N^2 \max_i{v_i}^2)\)

from collections import deque

# i番目の重みws[i], 価値vs[i], 個数ms[i]
def solve(N, W, ws, vs, ms):
    V0 = max(vs)
    V = sum(v * min(V0, m) for v, m in zip(vs, ms))

    # 各品物 min(max_j{v_j}, m_i) 個までの個数制限付きナップザック問題を解く
    dp = [W+1]*(V + 1)
    dp[0] = 0
    for i in range(N):
        v = vs[i]; w = ws[i]; m = ms[i]
        c = min(V0, m)
        ms[i] -= c
        for k in range(v):
            que = deque()
            push = que.append
            popf = que.popleft; popb = que.pop

            for j in range((V-k)//v+1):
                a = dp[k + j*v] - j * w
                while que and a <= que[-1][1]:
                    popb()
                push((j, a))

                p, b = que[0]

                dp[k + j*v] = b + j * w
                if que and p <= j-c:
                    popf()

    # 重さ単位における価値が大きい方から品物を並べる
    *I, = range(N)
    I.sort(key=lambda x: ws[x]/vs[x])
    *S, = [(vs[i], ws[i], ms[i]) for i in I]

    # 各価値ごとに、(W - wに貪欲に詰めた時の価値) + 価値v を求める
    def greedy():
        yield 0
        for i in range(V + 1):
            if dp[i] > W:
                continue
            rest = W - dp[i]
            r = i
            for v, w, m in S:
                m = min(m, rest // w)
                r += m * v
                rest -= m * w
            yield r
    return max(greedy())

Verified

  • AOJ: "DPL_1_I: Combinatorial - Knapsack Problem with Limitations II": source (Python3, 3.29sec)

  • AtCoder: "AtCoder Regular Contest 096 - F問題: Sweet Alchemy": source (PyPy3, 484ms)