空間最適化ナップサック
2 次元を 1 行に圧縮します
「空間最適化ナップサック」はCoddyKit上の無料Competitive Programming Academyレッスンです。 これはレッスン2/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCompetitive Programming Academy学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Competitive Programming Academyコースには全4レッスンが含まれています。
空間を最適化する理由
完全な表ではnかけるcapのメモリが必要になり、大きな入力では膨大になることがあります。空間最適化により、再利用する1行だけに縮小できます。
必要なのは直前の行だけ
各セルが参照するのは直前の行だけで、それより前の行は参照しないことに注目してください。そのため、表全体を一度に保存する必要はありません。
1つの配列に縮約する
長さcap+1のdp配列を1つだけ保持します。各品物を処理するとき、その配列を上書きして新しい行を表します。
dp = [0] * (cap + 1)再利用の落とし穴
容量を小さい方から大きい方へ走査すると、dp[w - wt[i]]が同じ品物についてすでに更新されている可能性があります。すると品物iを2回取れてしまいます。
容量を逆向きに走査する
これを防ぐには、容量を大きい方から小さい方へループします。逆向きに進めることで、dp[w - wt[i]]には直前の行の値が残ります。
for w in range(cap, wt[i] - 1, -1):
dp[w] = max(dp[w], val[i] + dp[w - wt[i]])逆向きが機能する理由
dp[w]を計算するとき、より小さいインデックスw - wt[i]はこのラウンドではまだ変更されていないため、意図したとおり直前の行を表します。
重さの位置で早めに止める
wt[i]未満の容量には品物を入れられないため、ループはwt[i]で止めます。そこを処理しないことで、不要な反復を省けます。
完全なループ
解全体は、1つの配列に対する2重ループです。外側で品物を処理し、内側で容量を逆向きに走査すると、答えが得られます。
for i in range(n):
for w in range(cap, wt[i] - 1, -1):
dp[w] = max(dp[w], val[i] + dp[w - wt[i]])最後のセルを読む
すべての品物を処理した後、dp[cap]に最大の価値が入ります。これは2次元の表で得られる値と同じですが、必要なメモリは大幅に少なくなります。
同じ時間で、より少ないメモリ
アルゴリズムが高速になったわけではなく、計算量は依然としてnかけるcapです。削減できるのはメモリで、二次から線形になります。
効果を発揮する場面
capが大きく、2次元の表ではメモリ制限を超えてしまう場合に、この方法が役立ちます。競技プログラミングでは覚えておくべき定番のテクニックです。
確認問題
1次元ナップサック問題の重要なルールを確認しましょう。
まとめ
2次元の表を1つの配列に縮約し、正しさを保つために容量を逆向きにループしました。これにより、二次のメモリ使用量を線形に削減できました。🚀
よくある質問
「空間最適化ナップサック」レッスンは無料ですか？
はい。「空間最適化ナップサック」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Competitive Programming Academyコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Competitive Programming Academyコースには全4レッスンが含まれています。
「空間最適化ナップサック」で何を学びますか？
2 次元を 1 行に圧縮します ブラウザで直接実行するハンズオンコードでCompetitive Programming Academyを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
Competitive Programming Academyを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのCompetitive Programming Academyは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン2/4です。
「空間最適化ナップサック」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このCompetitive Programming Academyレッスンでコードを書いて実行できますか？
はい。すべてのCompetitive Programming Academyレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。