Day 065-Q3 | 多次元DP + Roll最適化（次元削減・メモリ圧縮）

問題

$N$ 個のアイテムがあり、アイテム $i$ は重さ $w_i$、体積 $v_i$、価値 $p_i$ を持つ。重さ上限 $W$、体積上限 $V$ のナップサックに入れるとき：

選択個数制限なし: 価値の最大値
選択個数がちょうど $K$ 個: 価値の最大値

2つの値を出力せよ。メモリ使用量を $O(W \times V)$（$N$ に依存しない） に抑えた Roll 最適化を実装すること。

制約

パラメータ	範囲
$N$	$1 \le N \le 500$
$W, V$	$1 \le W, V \le 1000$
$K$	$1 \le K \le N$
$w_i, v_i, p_i$	$0 \le w_i \le W$, $0 \le v_i \le V$, $0 \le p_i \le 10^9$

入出力例

入力例 1

出力例 1

18
18

アイテム2+3: 重さ9, 体積9, 価値18。ちょうど2個でも同じ組み合わせが最適。

概念図: Roll最適化のメモリ削減

ヒント（段階的開示）

ヒント1: 方向性

3次元DP dp[i][j][k] = 最初の $i$ 個、重さ $j$、体積 $k$ を使った場合の最大価値。これを Roll（ローリング）最適化で $i$ 軸を削除し $O(W \times V)$ メモリで実現する。更新を逆順（降順）で行うことがポイント。

ヒント2: 個数制約付きDP

dp_k[cnt][j][k] = ちょうど cnt 個使用、重さ $j$、体積 $k$ の最大価値。cnt ループも逆順にすることで同一アイテムの多重カウントを防ぐ。初期値は-INF（実現不可能を表す）、dp_k[0][0][0] = 0。

ヒント3: コード骨格

INF = float('-inf')

# Part 1: 2D Knapsack with Roll
dp = [[INF]*(V+1) for _ in range(W+1)]
dp[0][0] = 0
for wi, vi, pi in items:
    for j in range(W, wi-1, -1):      # 逆順必須
        for k in range(V, vi-1, -1):  # 逆順必須
            if dp[j-wi][k-vi] != INF:
                dp[j][k] = max(dp[j][k], dp[j-wi][k-vi]+pi)

# Part 2: K個制約
dp_k = [[[INF]*(V+1) for _ in range(W+1)] for _ in range(K+1)]
dp_k[0][0][0] = 0
for wi, vi, pi in items:
    for cnt in range(K, 0, -1):        # cntも逆順
        for j in range(W, wi-1, -1):
            for k in range(V, vi-1, -1):
                if dp_k[cnt-1][j-wi][k-vi] != INF:
                    dp_k[cnt][j][k] = max(...)

模範解答 (Python)

import sys
input = sys.stdin.readline

def solve():
    N, W, V, K = map(int, input().split())
    items = []
    for _ in range(N):
        wi, vi, pi = map(int, input().split())
        items.append((wi, vi, pi))

    INF = float('-inf')

    # Part 1: 2D Knapsack with Roll optimization O(W*V) memory
    dp = [[INF] * (V + 1) for _ in range(W + 1)]
    dp[0][0] = 0

    for wi, vi, pi in items:
        for j in range(W, wi - 1, -1):
            for k in range(V, vi - 1, -1):
                if dp[j - wi][k - vi] != INF:
                    dp[j][k] = max(dp[j][k], dp[j - wi][k - vi] + pi)

    ans1 = max(dp[j][k] for j in range(W+1) for k in range(V+1) if dp[j][k] != INF)

    # Part 2: 2D Knapsack with exact K items
    dp_k = [[[INF] * (V + 1) for _ in range(W + 1)] for _ in range(K + 1)]
    dp_k[0][0][0] = 0

    for wi, vi, pi in items:
        for cnt in range(min(K, N), 0, -1):   # 逆順でcntループ
            for j in range(W, wi - 1, -1):
                for k in range(V, vi - 1, -1):
                    if dp_k[cnt - 1][j - wi][k - vi] != INF:
                        dp_k[cnt][j][k] = max(
                            dp_k[cnt][j][k],
                            dp_k[cnt - 1][j - wi][k - vi] + pi
                        )

    candidates = [dp_k[K][j][k] for j in range(W+1) for k in range(V+1)
                  if dp_k[K][j][k] != INF]
    ans2 = max(candidates) if candidates else 0

    print(ans1)
    print(ans2)

solve()

Step-by-Step 解説

Step 1: 2D ナップサックの状態空間

dp[j][k] = 重さ $j$ 以下、体積 $k$ 以下で実現できる最大価値。遷移は $O(N \times W \times V)$ で全体の計算量は変わらない。

Step 2: Roll 最適化の核心

通常の3Dテーブル dp[i][j][k] は $O(N \times W \times V)$ メモリを要する。しかし遷移で使うのは「直前の $i-1$ 行」のみ。更新を逆順（降順）で行うことで、未更新の旧値を参照し続けられる。

Step 3: 個数制約付き DP

dp_k[cnt][j][k] = ちょうど cnt 個使用、重さ $j$、体積 $k$ の最大価値。個数ループ cnt も逆順にすることで同一アイテムを複数回選ぶ問題を防ぐ（0/1 制約の保証）。

Step 4: 複数制約への拡張

次元	Roll後のメモリ
重さのみ	$O(W)$
重さ + 体積	$O(W \times V)$
重さ + 体積 + 個数	$O(K \times W \times V)$

Step 5: 計算量

処理	計算量
Part 1 時間	$O(N \times W \times V)$
Part 1 空間	$O(W \times V)$
Part 2 時間	$O(N \times K \times W \times V)$
Part 2 空間	$O(K \times W \times V)$

よくあるミス

ミス	原因	正しい書き方
逆順ループを忘れる	アイテムの多重選択が起きる	`range(W, wi-1, -1)` で降順に
初期値を 0 にする	「実現不可能」状態と区別できない	`-INF` で初期化、`dp[0][0] = 0`
cnt ループも逆順を忘れる	同一アイテムが複数回カウントされる	`range(K, 0, -1)` で降順に
ans2 の候補がゼロ件	ちょうど K 個選べない入力	`max(...) if candidates else 0`

次のステップ

発展問題: 同種アイテムが複数個あり「アイテム種 $i$ を最大 $c_i$ 個まで」選べる有界ナップサックを、Binary Grouping または Monotone Queue Deque で $O(N \times W \times V \times \log(\max c_i))$ に最適化せよ。

自己評価

完全理解おおむね理解要復習