後述のアルゴリズムの問題で問題があります。
ある港に 3 車線のフェリーがあり、その前に N 台の車が並んでいます。それぞれにcm単位で指定された長さがあります。また、フェリーの長さ (L) もわかっています。キューから最大量の車をフェリーに積み込むことができるアルゴリズムを提案する必要があります。各車は、左、中央、または右の 3 つの車線のいずれかを選択できます。車は順番に処理する必要があります - 各車 (先頭から開始) について、どの車線を走行するかを決定する必要があります。キューの前にある車に十分な空きスペースがない場合は、終了します。残りの車両は次のフェリーを待ちます。
貪欲な方法 (first-fit) は、すべての場合で最も効率的というわけではありません (たとえば、L が 5 でキューが 5 2 2 3 3 の場合)。したがって、動的計画法の問題と考える場合、解決策は何かを理解しようとしていました。それでも私は何かを見つけようとしていますが、私が知っているすべての動的アルゴリズム(特にアルゴリズムの紹介から)はその問題に適合していないようです。
ご提案いただきありがとうございます。:)