私はアルゴリズムに不慣れで、現在YouTubeのビデオチュートリアル/講義と本を使用して勉強しています。最初にビデオを見てから本を読み、最後に本から質問をして、トピックを正しく学習したことを確認します。私は現在、欲張りアルゴリズムに取り組んでおり、非常に混乱しています。
本の中にはいろいろな問題がありますが、特定の問題を理解して答えるのに苦労しています。
まず、問題が発生します（テキストをコピーしました）。
サイズが{x1;のn個のオブジェクトのセットがあります。x2;.....xn}と容量Bのビン。これらはすべて正の整数です。これらのオブジェクトのサブセットを見つけて、それらの合計サイズがB以下になるようにしますが、可能な限りBに近づけます。
すべてのオブジェクトは1次元です。たとえば、オブジェクトのサイズが4、7、10、12、15、およびB = 20の場合、合計サイズが19（または同等に7と12）の4と15を選択する必要があります。次の欲張りアルゴリズムのそれぞれについて、反例を作成して、それらが最適ではないことを示します。例をできるだけ悪くするようにしてください。「悪さ」は、最適なソリューションと貪欲なソリューションの比率によって測定されます。したがって、最良の解の値が10で、欲張り解の値が5の場合、比率は2になります。
次の場合、どうすればよいですか？
1）このオブジェクトとすでに選択されている他のすべてのオブジェクトの合計サイズがBを超えないように、常に最大サイズのオブジェクトを選択します。残りのオブジェクトについてもこれを繰り返します。