Coding Interview Prep · レッスン

0/1ナップサックと空間最適化

Q: 「0/1ナップサックと空間最適化」レッスンは無料ですか？

はい。「0/1ナップサックと空間最適化」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Coding Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Coding Interview Prepコースには全4レッスンが含まれています。

Q: 「0/1ナップサックと空間最適化」で何を学びますか？

0/1ナップサックの漸化式を導き、2次元テーブルを埋めた後、容量を逆順に走査して1次元配列に圧縮します。 ブラウザで直接実行するハンズオンコードでCoding Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。

Q: Coding Interview Prepを始めるのに経験は必要ですか？

事前経験は必要ありません。CoddyKitのCoding Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン1/4です。

Q: 「0/1ナップサックと空間最適化」レッスンにはどのくらい時間がかかりますか？

ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。

Q: このCoding Interview Prepレッスンでコードを書いて実行できますか？

はい。すべてのCoding Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。

0/1ナップサックの漸化式を導き、2次元テーブルを埋めた後、容量を逆順に走査して1次元配列に圧縮します。

「0/1ナップサックと空間最適化」はCoddyKit上の無料Coding Interview Prepレッスンです。これはレッスン1/4です。下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。これはCoding Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Coding Interview Prepコースには全4レッスンが含まれています。

0/1ナップサック問題

0/1ナップサック問題とは、重さ w[i] と価値 v[i] をそれぞれ持つ n 個の品物と、容量 W のナップサックが与えられたとき、容量を超えずに価値の合計を最大化するよう品物を選ぶ問題です。各品物はちょうど1回だけ選択します（0 = 選ばない、1 = 選ぶ）。これは、partition-equal-subset-sum や target-sum など、面接で問われるDP問題の大きな体系の原型です。

DPの状態と漸化式

dp[i][c] を、最初の i 個の品物から容量 c 以内で得られる価値の最大値と定義します。品物 i については、選ばない（dp[i-1][c]）か、w[i] <= c の場合に選ぶ（dp[i-1][c-w[i]] + v[i]）かの2通りがあります。漸化式は、w[i] <= c のとき dp[i][c] = max(dp[i-1][c], dp[i-1][c-w[i]] + v[i])、それ以外の場合は dp[i][c] = dp[i-1][c] です。基底条件は、すべての c に対して dp[0][c] = 0 です。

2次元DPテーブルの実装

2次元テーブルには (n+1) x (W+1) 個の要素があり、品物ごとに行単位で埋めていきます。すべての行を埋め終えると、dp[n][W] に価値の最大値が格納されます。計算量は時間 O(n × W)、空間 O(n × W)です。これは擬多項式計算量であり、Wが小さい場合に効率的です。

def knapsack_2d(weights, values, W):
    n = len(weights)
    dp = [[0]*(W+1) for _ in range(n+1)]
    
    for i in range(1, n+1):
        w, v = weights[i-1], values[i-1]
        for c in range(W+1):
            dp[i][c] = dp[i-1][c]  # skip item i
            if c >= w:
                dp[i][c] = max(dp[i][c], dp[i-1][c-w] + v)
    
    return dp[n][W]

weights = [2, 3, 4, 5]
values  = [3, 4, 5, 6]
print(knapsack_2d(weights, values, 8))  # 10

1次元DPで容量を逆順に走査する理由

重要なポイントは、行 i が行 i-1 にのみ依存していることです。そのため、1つの1次元配列を使って、その場で更新できます。ただし、容量 c を左から右（小さい順）に走査すると、品物 i が2回数えられる可能性があります。すでに品物 i を含んでいる、c-w[i] の更新済みの値を使ってしまうためです。右から左（大きい順）に走査すれば、各行の更新で各品物が高々1回しか使われないことが保証されます。

# Forward iteration (WRONG for 0/1 knapsack - counts items multiple times)
# for c in range(W+1):
#     dp[c] = max(dp[c], dp[c-w] + v)   <-- dp[c-w] may already use item i

# Backward iteration (CORRECT for 0/1 knapsack)
# for c in range(W, w-1, -1):
#     dp[c] = max(dp[c], dp[c-w] + v)   <-- dp[c-w] still from previous row

1次元に空間最適化した実装

配列を1つだけ保持し、容量を W から w[i] まで降順に走査することで、空間 O(W) で2次元テーブルと同じ結果を得られます。時間計算量は O(n × W) のままです。この空間最適化は必ず覚えておくべき重要事項です。面接では、2次元のナップサックDPを1次元に削減するよう頻繁に求められます。

def knapsack_1d(weights, values, W):
    dp = [0] * (W + 1)
    
    for i in range(len(weights)):
        w, v = weights[i], values[i]
        for c in range(W, w - 1, -1):  # iterate RIGHT TO LEFT
            dp[c] = max(dp[c], dp[c - w] + v)
    
    return dp[W]

weights = [2, 3, 4, 5]
values  = [3, 4, 5, 6]
print(knapsack_1d(weights, values, 8))  # 10

選択した品物の復元

どの品物を選択したかを求めるには、完全な2次元テーブルが必要です。テーブルを埋めた後、dp[n][W] から始めて逆向きにたどります。dp[i][c] != dp[i-1][c] なら、品物 i が選択されています。その場合は重さを c から引き、行 i-1 に移動します。i = 0 になるまで続けます。1次元最適化では、この復元機能が失われます。

def knapsack_with_items(weights, values, W):
    n = len(weights)
    dp = [[0]*(W+1) for _ in range(n+1)]
    for i in range(1, n+1):
        w, v = weights[i-1], values[i-1]
        for c in range(W+1):
            dp[i][c] = dp[i-1][c]
            if c >= w:
                dp[i][c] = max(dp[i][c], dp[i-1][c-w] + v)
    
    # Reconstruct
    selected, c = [], W
    for i in range(n, 0, -1):
        if dp[i][c] != dp[i-1][c]:
            selected.append(i-1)
            c -= weights[i-1]
    return dp[n][W], selected[::-1]

print(knapsack_with_items([2,3,4,5],[3,4,5,6],8))

実践例：価値の合計を最大化する

品物が次のように与えられているとします：weights=[2,3,4,5]、values=[3,4,5,6]、W=8。最適解は、重さ3（価値4）と重さ5（価値6）の品物を選ぶ方法で、重さの合計は8、価値の合計は10です。重さ2と5を選ぶと価値の合計は9、重さ2と3を選ぶと価値は7です。DPは正しく最大値10を求めます。貪欲法（価値と重さの比率が最も高いものを選ぶ方法）では、比率1.5の品物（重さ2、価値3）を最初に選びますが、これが常に最適とは限らない点に注意してください。

分割ナップサックと0/1ナップサックの比較

分割ナップサックでは、品物の一部だけを選択できます。この問題は、価値と重さの比率でソートする貪欲法によって解けます。一方、0/1ナップサックでは品物を分割できないため、貪欲法は通用せず、DPが必要です。面接ではこの違いを使って、貪欲法をいつ適用できるかを理解しているか確認します。分割版について聞かれたら、すぐにソートを用いた貪欲法に言及し、0/1版ならDPを使います。

# Fractional knapsack: greedy by value/weight ratio
def fractional_knapsack(weights, values, W):
    items = sorted(zip(values, weights), key=lambda x: x[0]/x[1], reverse=True)
    total = 0
    for v, w in items:
        if W >= w:
            total += v; W -= w
        else:
            total += v * (W / w); break
    return total

print(fractional_knapsack([2,3,4,5],[3,4,5,6],8))

擬多項式時間計算量

0/1ナップサックはNP完全ですが、O(nW)時間で解けます。この矛盾は、O(nW)が擬多項式であることで解消されます。Wは入力サイズではなく値だからです。Wの2進表現には O(log W) ビットが必要なので、真の計算量は O(n × 2^(log W)) となり、入力サイズに対して指数時間です。Wが小さい場合（例：10⁴）はDPが実用的ですが、Wが10⁹にもなり得る場合は別の手法が必要です。

面接での追加質問：大きな容量

面接で W が非常に大きい（例：10⁹）一方で n が小さいという条件を出された場合、標準的なDPは使えません。代替手法には、(1) O(2^(n/2) × n) 時間のミート・イン・ザ・ミドル、(2) 分割版に対する貪欲近似法、(3) 分枝限定法があります。W <= 10⁵ の面接問題の多くでは、容量を逆順に走査する1次元DPが期待される解答です。

大きな容量に対するミート・イン・ザ・ミドル

W が非常に大きく n が小さい場合（例：n=40）、標準的な O(nW) DPは実行できませんが、全探索の 2^n も遅すぎます。ミート・イン・ザ・ミドルでは、品物を2つの半分に分け、それぞれについて 2^(n/2) 個の部分集合を列挙し、最適な組み合わせを求めます。一方の半分を重さでソートし、もう一方の各部分集合について、容量内で組み合わせられる最適な相手を二分探索で探します。計算量は O(2^(n/2) × n) で、nが40程度までなら実用的です。

理解度チェック

このレッスンで学んだ Data Structures & Algorithms — Coding Interview Prep の概念について、理解度を確認しましょう。

レッスンのまとめ

このレッスンでは、0/1ナップサックDPでは、i個の品物と容量cにおける価値の最大値を dp[i][c] で表すこと、各品物を選ばないか選ぶかで漸化式を構成すること、そして1次元への空間最適化では、品物の二重カウントを防ぐため容量を右から左に走査することを学びました。次は、品物を再利用できる非制限ナップサックを学び、それを Coin Change II に応用します。

よくある質問