Knapsack Problem
概要
以下のような問題
-
\(N\) 種類の品物がある
-
\(i\) 番目の品物の価値は \(v_i\), 容量は \(w_i\), 個数は \(c_i\)
-
重さの総和 \(W\) まで入るナップサックに入れる
-
ナップサックに入る品物の価値を最大化する
0-1ナップサック問題: \(O(N^2 \max_i{v_i})\)
制約の一例は以下
各価値 \(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})\)
制約の一例は以下
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)\)
制約の一例は以下
-
各品物 \(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)\)
-
-
(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())