0Pricing
Competitive Programming Academy · レッスン

非有界ナップサックとコイン交換 DP

項目を何度でも使えるようにします

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

無制限の品物

無制限ナップサックでは、各品物を好きなだけ何度でも選べます。決まった品物の山ではなく、自動販売機のコインをイメージしてください。

たった1つの変更

0/1ナップサックとの違いは、ループの方向だけです。無制限に選べる場合は、容量を順方向、つまり小さい方から大きい方へ走査します。

順方向の再利用がポイント

順方向に進めると、dp[w - coin]に同じ品物をすでに含められます。この意図した再利用によって、その品物をもう一度選べます。

コイン交換問題を知る

典型的なコイン交換問題では、ある金額を作るために必要なコインの最小枚数を求めます。これは、最大値の代わりに最小値を使う無制限DPです。

状態を定義する

dp[a]を、金額aを作るために必要なコインの最小枚数とします。0はコインなしで作れるため、dp[0] = 0から始めます。

dp = [float("inf")] * (amount + 1)
dp[0] = 0

不可能な場合は無限大を使う

到達できない金額は無限大で初期化します。最後まで無限大のままなら、どのコインの組合せでもその金額を作れません。

遷移

各コインについて、そのコインで到達できるすべての金額を改善できるか試します。残った小さい方の金額の最適値に、コイン1枚分を加えます。

for coin in coins:
    for a in range(coin, amount + 1):
        dp[a] = min(dp[a], dp[a - coin] + 1)

順方向にする理由

金額を小さい方から走査すると、dp[a - coin]にこのコインをすでに数えた値を利用できます。これにより、1枚のコインを複数回使えます。

通り数を数える場合

min+1の代わりに合計を使うと、各金額を作る方法の数を数えられます。コインのループを外側に置けば、順序を重複して数えません。

for coin in coins:
    for a in range(coin, amount + 1):
        dp[a] += dp[a - coin]

結果を読む

答えはdp[amount]に入ります。最小枚数版では、無限大の値は目標金額を作れないことを意味します。

0/1と無制限

切り替えるのは1点だけです。容量を逆向きに走査すると各品物を1回だけ使い、順方向に走査すると無制限に使えます。同じ表でも、走査方向が反対になります。

確認問題

ナップサック問題を無制限にする要素を確認しましょう。

まとめ

無制限に再利用できるようループを順方向に切り替え、最小枚数を求めるmin版または総通り数を求める合計版でコイン交換問題を構築しました。💰

よくある質問

「非有界ナップサックとコイン交換 DP」レッスンは無料ですか？

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

「非有界ナップサックとコイン交換 DP」で何を学びますか？

項目を何度でも使えるようにします ブラウザで直接実行するハンズオンコードでCompetitive Programming Academyを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。

Competitive Programming Academyを始めるのに経験は必要ですか？

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

「非有界ナップサックとコイン交換 DP」レッスンにはどのくらい時間がかかりますか？

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

このCompetitive Programming Academyレッスンでコードを書いて実行できますか？

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

このコースのすべてのレッスン

  1. 0/1 ナップサック: 選ぶか選ばないか
  2. 空間最適化ナップサック
  3. 非有界ナップサックとコイン交換 DP
  4. 部分集合和と分割
← Competitive Programming Academyに戻る