0Pricing
Coding Interview Prep · レッスン

比率による分割可能ナップサック

重量あたりの価値が最も高いものから選びます

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

ナップサック問題の設定

価値と重さを持つ品物と、限られた容量のバッグがあります。目標は、運べる価値の合計を最大にすることです。🎒

分割可能であること

分数版では、穀物の袋を半分だけ取るように、品物の一部を取ることができます。この自由度が、ここで貪欲法を使える理由です。

重さあたりの価値

重要な指標は、各品物の価値と重さの比率です。比率が高いほど、少ない空間に多くの価値が詰まっています。

ratio = value / weight

最良の比率でソートする

品物を価値と重さの比率が高い順にソートします。貪欲法では、利用可能な中で最も価値密度の高いものを順に選びます。

items.sort(key=lambda i: i[0] / i[1], reverse=True)

入る間は丸ごと取る

ソート済みのリストを走査し、残りの容量に入るなら各品物を完全に取ります。その品物の価値全体を合計に加えます。

if weight <= cap:
    total += value
    cap -= weight

最後の隙間を埋める

品物が大きすぎる場合は、残った空間をちょうど埋める一部だけを取ります。これでバッグが満杯になるため、処理を終了します。

total += value * (cap / weight)

比率の順番が機能する理由

容量1単位には可能な限り大きな価値を入れるべきなので、最も価値密度の高い品物を先に選ぶ必要があります。密度の低い品物に置き換えると、価値が下がるだけです。

0/1ナップサックは別物

アイテムを分割できない場合、比率による貪欲法は破綻します。0/1版には、この単純な並べ替えではなく動的計画法が必要です。

実行時間

比率による並べ替えにはO(n log n)かかり、詰めるループは線形時間です。一般的なコンテストの制限時間なら十分に高速です。

最後の分数に注意

一部だけ取るアイテムには、浮動小数点数か正確な有理数を使ってください。早く切り捨てると価値が減り、誤答の原因になります。

登場する場面

貨物の積み込み、燃料の混合、資源の分割などを考えてみてください。分割可能なものを扱うときは、比率による貪欲法が役立ちます。

クイックチェック

分割可能ナップサック問題で、バッグにアイテムを詰めています。

まとめ

アイテムを重さあたりの価値で並べ替え、入る間はアイテム全体を取り、最後に一部を取ってバッグを満たします。この貪欲法が最適なのは、アイテムを分割できる場合だけです。🚀

よくある質問

「比率による分割可能ナップサック」レッスンは無料ですか？

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

「比率による分割可能ナップサック」で何を学びますか？

重量あたりの価値が最も高いものから選びます ブラウザで直接実行するハンズオンコードでCoding Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。

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

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

「比率による分割可能ナップサック」レッスンにはどのくらい時間がかかりますか？

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

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

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

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

  1. 貪欲法の考え方
  2. 終了時刻が早い順のアクティビティ選択
  3. 比率による分割可能ナップサック
  4. 貪欲法が失敗する場合を見抜く
← Coding Interview Prepに戻る