Knapsack Problem

概要

以下のような問題

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

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

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

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

0-1ナップサック問題: \(O(NW)\)

制約の一例は以下

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

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

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

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

  • \(c_i = 1\)

基本的な制約。

一次配列を用いたdpで、インデックス逆から回す。

# i番目の重みws[i], 価値vs[i]
def solve(N, W, ws, vs):
    dp = [0] * (W+1)
    for i in range(N):
        # 価値v, 重さw
        v = vs[i]; w = ws[i]
        for j in range(W, w-1, -1):
            dp[j] = max(dp[j-w] + v, dp[j])
    return max(dp)

Verified

  • AOJ: "DPL_1_B: Combinatorial - 0-1 Knapsack Problem": source (Python3, 0.52sec)

個数制限なしナップサック問題: \(O(NW)\)

制約の一例は以下

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

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

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

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

  • (\(c_i\) は無制限)

一次配列を用いたdpで、インデックス順に回せばよい。

# i番目の重みws[i], 価値vs[i]
def solve(N, W, ws, vs):
    dp = [0] * (W+1)
    for i in range(N):
        # 価値v, 重さw
        v = vs[i]; w = ws[i]
        for j in range(w, W+1):
            dp[j] = max(dp[j-w] + v, dp[j])
    return max(dp)

Verified

  • AOJ: "DPL_1_C: Combinatorial - Knapsack Problem": source (Python3, 0.55sec)

個数制限付きナップサック問題: \(O(NW)\)

制約の一例は以下

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

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

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

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

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

dequeを用いたSliding Window Maximumを利用した解法
各 \(0 \le k < w_i\) ごとに \(m_i\) 個前までの価値の最大値を管理しながら、重さが \(k + w_i \cdot j\) の時の価値の最大値を計算する。

from collections import deque

# i番目の重みws[i], 価値vs[i], 個数ms[i]
def solve(N, W, ws, vs, ms):
    S = [0]*(W+1)
    for i in range(N):
        # 価値v, 重さw, 個数m
        v = vs[i]; w = ws[i]; m = ms[i]
        for k in range(w):
            # 0 ≤ k ≤ w-1
            que = deque()
            for j in range((W - k) // w + 1):
                # 各 p = k + j*w について計算
                # 重さpの価値を重さkを基準にして管理するため、(価値v) × j を引く
                # (重さpの価値は重さkのものにi番目の品物をj個入れたものとみなす)
                v0 = S[k + j*w] - j*v
                while que and que[-1][1] <= v0:
                    que.pop()
                que.append((j, v0))

                # 重さp の価値の最大 = (区間内について、重さkを基準にした価値の最大) + (価値v) × j
                S[k + j*w] = que[0][1] + j*v

                # m個前の要素を取り除く
                if que and que[0][0] <= j-m:
                    que.popleft()
    return max(S)

Verified

  • AOJ: "DPL_1_G: Combinatorial - Knapsack Problem with Limitations": source (Python3, 1.46sec)

個数制限付きナップサック問題: \(O(NW \log \max_i c_i)\)

各品物を \(c_i = 2^0 + 2^1 + ... + 2^{k-1} + 2^k + R\) (\(R \le 2^{k+1}\)) という感じに分け、
分けた品物ごとに1つの品物(\(A\) 個の品物は 重さ \(w_i \cdot A\), 価値 \(v_i \cdot A\) の1つの品物)とみなすことで、
品物が \(O(N \log \max_i c_i)\) 個の0-1ナップサック問題として解くことができる。

def solve(N, W, ws, vs, ms):
    vs0 = []; ws0 = []
    for i in range(N):
        v = vs[i]; w = ws[i]; m = ms[i]
        b = 1
        while b <= m:
            vs0.append(v * b)
            ws0.append(w * b)
            m -= b
            b <<= 1
        if m:
            vs0.append(v * m)
            ws0.append(w * m)

    dp = [0] * (W+1)
    N0 = len(vs0)
    for i in range(N0):
        v = vs0[i]; w = ws0[i]
        for j in range(W, w-1, -1):
            dp[j] = max(dp[j-w] + v, dp[j])
    return max(dp)

Verified

  • AOJ: "DPL_1_G: Combinatorial - Knapsack Problem with Limitations": source (Python3, 4.32sec)

戻る