非有界ナップサックとCoin Change II
容量を順方向に走査してアイテムの再利用を可能にし、この変形を使ってcoin-change-II（方法の数）とrod-cuttingを解きます。
「非有界ナップサックとCoin Change II」はCoddyKit上の無料Coding Interview Prepレッスンです。 これはレッスン2/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCoding Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Coding Interview Prepコースには全4レッスンが含まれています。
非制限ナップサックの概念
非制限ナップサックでは、各品物を何度でも選択できます（各品物を高々1回しか使えない0/1ナップサックとは異なります）。状態の定義は同じで、dp[c] = 容量 c で達成できる価値の最大値です。ただし、走査方向が変わります。品物を再利用できるため、dp[c] を更新するときに現在の品物をもう一度使えるよう、容量を左から右（昇順）に走査します。
前向きの走査による再利用
0/1ナップサックでは再利用を防ぐため、右から左に走査したことを思い出してください。非制限ナップサックでは逆に、左から右に走査します。dp[c] を計算するとき、dp[c-w] は現在の走査ですでに更新されています。つまり、品物 i がすでに含まれている可能性があります。これはまさに意図した動作です。品物 i をすでに含む解に、品物 i をもう一度追加できるからです。
def unbounded_knapsack(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): # iterate LEFT TO RIGHT
dp[c] = max(dp[c], dp[c - w] + v)
return dp[W]
weights = [1, 3, 4, 5]
values = [1, 4, 5, 7]
print(unbounded_knapsack(weights, values, 7)) # 9Coin Change II：方法の数を数える
Coin Change IIでは、コインの額面と金額が与えられたとき、その金額を作る異なる方法の数を求めます（各コインは何度でも使用できます）。これは非制限ナップサックの変形で、価値を最大化する代わりに組み合わせの数を数えます。dp[c] を金額 c を作る方法の数と定義します。基底条件は dp[0] = 1 です（0を作る方法は何も選ばない1通りです）。
Coin Change IIの実装
各コインについて、金額を左から右に走査し、次のように累積します：dp[c] += dp[c - coin]。基底条件 dp[0] = 1 が個数の計算の起点になります。外側のループをコイン、内側のループを金額にする点に注意してください。各コインの額面が外側のループで1回だけ処理されるため、これにより組み合わせの数（順列ではありません）が自然に求まります。
def change(amount, coins):
dp = [0] * (amount + 1)
dp[0] = 1 # one way to make amount 0
for coin in coins:
for c in range(coin, amount + 1):
dp[c] += dp[c - coin]
return dp[amount]
print(change(5, [1, 2, 5])) # 4
print(change(3, [2])) # 0
print(change(10, [10])) # 1組み合わせと順列
ループの順序は非常に重要です。外側のループを金額、内側のループをコインにすると、順列（順序を区別する）を数えます。amount=5、コイン [1,2] の場合、1+2+2 と 2+1+2 は別々に数えられます。外側のループをコインにすると、組み合わせ（順序を区別しない）を数えます。1+2+2 と 2+1+2 は同じものとして扱われます。Coin Change IIが求めるのは組み合わせなので、コインを外側のループにします。
# Count COMBINATIONS (order does not matter) — coin outer loop
def combinations(amount, coins):
dp = [0] * (amount + 1)
dp[0] = 1
for coin in coins: # coin outer
for c in range(coin, amount + 1):
dp[c] += dp[c - coin]
return dp[amount]
# Count PERMUTATIONS (order matters) — amount outer loop
def permutations(amount, coins):
dp = [0] * (amount + 1)
dp[0] = 1
for c in range(1, amount + 1): # amount outer
for coin in coins:
if c >= coin:
dp[c] += dp[c - coin]
return dp[amount]
print(combinations(5, [1,2,5])) # 4
print(permutations(5, [1,2,5])) # 13ロッドカッティング問題
もう1つの典型的な非制限ナップサック問題です。長さ n の棒と、長さ1からnまでの各棒の価格が与えられたとき、棒を最適に切断して得られる収益の最大値を求めます。長さ l の各 parç は price[l] で販売でき、同じ長さの parç を何個でも作れます（棒を同じ長さの複数の parç に切断できます）。これは、W = n とし、異なる切断長を品物とする非制限ナップサックにそのまま対応します。
def rod_cutting(prices, n):
# prices[i] = price of rod of length i+1
dp = [0] * (n + 1)
for length in range(1, n + 1): # each cut length
price = prices[length - 1]
for c in range(length, n + 1):
dp[c] = max(dp[c], dp[c - length] + price)
return dp[n]
prices = [1, 5, 8, 9, 10, 17, 17, 20]
print(rod_cutting(prices, 8)) # 22Coin Change I：最小コイン数
Coin Change I（別の問題）では、目標金額を作るために必要なコインの最小枚数を求めます。ここでは dp[c] = 金額 c を作るための最小コイン数です。漸化式は dp[c] = min(dp[c], dp[c - coin] + 1) です。dp[0] = 0 以外のすべての要素を inf で初期化します。これも非制限型（コインを再利用可能）なので、左から右に走査します。dp[amount] が有限値ならその値を返し、そうでなければ -1 を返します。
def coinChange(coins, amount):
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for coin in coins:
for c in range(coin, amount + 1):
dp[c] = min(dp[c], dp[c - coin] + 1)
return dp[amount] if dp[amount] != float('inf') else -1
print(coinChange([1,5,6,9], 11)) # 2 (5+6 or other combos)
print(coinChange([2], 3)) # -1重要な違い：最大化・最小化・個数の計算
非制限ナップサックの3つの変形では、dp[c-coin] に対する操作が異なります。価値を最大化：dp[c] = max(dp[c], dp[c-w] + v)。0で初期化します。コストを最小化：dp[c] = min(dp[c], dp[c-coin] + 1)。inf で初期化し、dp[0]=0 とします。方法の数を数える：dp[c] += dp[c-coin]。0で初期化し、dp[0]=1 とします。どの変形を適用すべきかを見極めることが、面接問題を解くうえで重要なポイントです。
計算量と面接のヒント
非制限ナップサックのすべての変形は、品物の種類数をn、目標金額をWとすると、時間 O(n × W)、空間 O(W) で実行できます。コイン問題では、nはコインの額面の種類数です。面接では、変形（最大化・最小化・個数）を明示し、1次元DPを書き、外側のループがコインか金額かを明確にしてください。面接官は、この違いによってDPを深く理解しているかを確認します。
非制限型と0/1型の見分け方
どの変形を使うかは、次の手がかりで判断します。無制限に再利用できる → 非制限型（前向きに走査）、各品物をちょうど1回だけ使う → 0/1型（逆向きに走査）、問題文に「何度でも使える」「無限に供給される」「再利用可能」とある → 非制限型です。例として、コイン交換、ロッドカッティング、整数分割はすべて非制限型です。部分和、分割、0/1ナップサックは0/1型です。ここを間違えると、デバッグが難しい誤答につながります。
Integer Breakとその他の変形
Integer Break（LeetCode 343）は、整数nを2個以上の正の整数に分割し、その積を最大化する問題です。これは、「品物」を2からn-1までの整数とする非制限ナップサックです。dp[i] を、合計がiになる整数の積の最大値と定義します。各品物jについて2からiまで、dp[i] = max(dp[i], max(j, dp[j]) * max(i-j, dp[i-j])) とします。この例から、非制限型のパターンがコイン以外の問題にも一般化できることが分かります。
def integerBreak(n):
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
for j in range(1, i):
dp[i] = max(dp[i], max(j, dp[j]) * max(i-j, dp[i-j]))
return dp[n]
print(integerBreak(10)) # 36 (3+3+4 = 3*3*4 = 36)理解度チェック
このレッスンで学んだ Data Structures & Algorithms — Coding Interview Prep の概念について、理解度を確認しましょう。
レッスンのまとめ
このレッスンでは、非制限ナップサックでは品物の再利用を可能にするため容量を左から右に走査すること、Coin Change IIではコインを外側のループに置くことで組み合わせの数を数えること、そして3つの変形（最大化・最小化・個数の計算）は、DPでの操作と初期化だけが異なることを学びました。次は0/1ナップサックを使って、Partition Equal Subset Sumを解きます。
よくある質問
「非有界ナップサックとCoin Change II」レッスンは無料ですか？
はい。「非有界ナップサックとCoin Change II」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Coding Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Coding Interview Prepコースには全4レッスンが含まれています。
「非有界ナップサックとCoin Change II」で何を学びますか？
容量を順方向に走査してアイテムの再利用を可能にし、この変形を使ってcoin-change-II（方法の数）とrod-cuttingを解きます。 ブラウザで直接実行するハンズオンコードでCoding Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
Coding Interview Prepを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのCoding Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン2/4です。
「非有界ナップサックとCoin Change II」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このCoding Interview Prepレッスンでコードを書いて実行できますか？
はい。すべてのCoding Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。
このコースのすべてのレッスン
- 0/1ナップサックと空間最適化
- 非有界ナップサックとCoin Change II
- Partition Equal Subset Sum
- 正負の符号を使うTarget Sum