0Pricing
Competitive Programming Academy · レッスン

0/1 ナップサック: 選ぶか選ばないか

重量制限の下で価値を最大化します

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

ナップサック問題の物語

重さの上限がある袋と、いくつかの品物があります。0/1ナップサック問題では、袋に詰め込みすぎずに価値を最大化する品物を選びます。🎒

取るか、残すか

0/1とは、各品物を完全に取るか、完全に残すかのどちらかだという意味です。品物を半分だけ取ることはできないため、選択肢は yes か no になります。

貪欲法が失敗する理由

最も安い品物や最も価値の高い品物から取ると、容量を無駄にすることがあります。ここでは貪欲法による近道は通用しないため、実際の組合せを考える必要があります。

2つの入力

各品物の重さと価値を並べた2つのリストと、1つの容量が与えられます。品物iの重さはwt[i]、価値はval[i]です。

wt  = [1, 3, 4, 5]
val = [1, 4, 5, 7]
cap = 7

状態を定義する

dp[i][w]を、最初のi個の品物から容量w以内で選べる最大の価値とします。状態を正確に名付けることが、この問題の核心です。

残す選択

品物iを残す場合、価値はすでに得ていた値、つまりdp[i-1][w]です。残りの品物に使える容量は変わりません。

取る選択

品物iを取る場合は、その価値を加えて容量を減らします。式はval[i] + dp[i-1][w - wt[i]]です。ただし、wがwt[i]以上の場合に限り選べます。

より良い分岐を選ぶ

漸化式では、2つの選択肢のうち大きい方をmaxで残します。各セルは、その下ですでに計算された答えを利用します。

dp[i][w] = max(dp[i-1][w],
               val[i] + dp[i-1][w - wt[i]])

基底行

品物が0個なら、どの容量でも運べる価値は0です。このベースケースによって、最初の行をすべて0で埋め、そこから計算を始めます。

dp = [[0] * (cap + 1) for _ in range(n + 1)]

表を埋める

外側のループで品物を、内側のループで容量を処理します。各セルは直前の行だけを参照するため、1回の走査ですべてを埋められます。

for i in range(1, n + 1):
    for w in range(cap + 1):
        dp[i][w] = dp[i-1][w]

答えを読む

右下のセルdp[n][cap]に、すべての品物と容量全体を対象とした最大の価値が入ります。この1つのセルが最終的な答えです。

確認問題

0/1ナップサック問題の基本的な漸化式を確認しましょう。

まとめ

0/1ナップサック問題では、各品物を取るか残すかを選び、dp[i][w]には残す場合と取る場合のうち最善の値を保存し、答えはdp[n][cap]になることを学びました。🎉

よくある質問

「0/1 ナップサック: 選ぶか選ばないか」レッスンは無料ですか？

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

「0/1 ナップサック: 選ぶか選ばないか」で何を学びますか？

重量制限の下で価値を最大化します ブラウザで直接実行するハンズオンコードでCompetitive Programming Academyを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。

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

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

「0/1 ナップサック: 選ぶか選ばないか」レッスンにはどのくらい時間がかかりますか？

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

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

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

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

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