オンラインで稼働した0-1ナップザック問題を効率的に解決します

Question

$ n $ 項目、サイズ $ b $ 単位のビン。各項目 $ J $ の消費 $ w_j $ $の単位B $ ナップザックに入れると。アイテムはオンラインファッションで1つずつ表示されます。項目 $ i $ が表示されたら、それをビンに配置する必要があります（取り消し可能）、または無視する必要があります。目的は、ビンに配置されたアイテムの数を最大化することです。 （すべての入力は正の整数です。）

オフラインアルゴリズムは簡単です。 $ w_1 \ leq w_2 \ leq \ cdots \ leq w_n $ にある項目を置きます。

この問題をオンラインファッションで解決するにはどうすればよいですか。私のアプローチは選択肢をランダム化することです： $ j $ が表示され、それを確率でbinに置く $ p_j $ < / SPAN>それ以外の場合は無視してください。

Answer 1

あなたがすでに気づいたと少なくとも言及されていなかったので、あなたの問題のために決定論的な競争的なアルゴリズムがないことがわかりやすいです。（CounterExamplesは2つの項目だけを必要とし、アルゴリズムが決定論的であるという事実を使用することができます。）

あなたのアプローチは、ランダム化によって克服できないといういくつかの困難を克服することはできませんので実際には十分ではありません。しかし、あなたの問題のいくつかの緩和モデルがあります。

これらのいくつか、そして私の答えの詳細は、Susanne Albers、Arindam KhanとLeon Ladewigという用紙にあります。