アンチビンパッキング

私は、(実質的に)無制限の量のマクドナルドクーポンを持っています。少なくとも1つのお金を買う場合にのみ使用できます。
したがって私は家族の食事をできるだけ多くの部分に分割して、すべて少なくとも1に値するようにしたいと考えています。
この問題の複雑さについては何が分かっていますか?

ps。価格は一般的に長い数字なので、単数で与えられるとは思わないでください!

ベストアンサー

この問題をビン被覆といいます。部分集合和から簡単に減らすことによって2倍以上に近づくのは難しいですが、漸近近似スキーム($(1-
ε) mathrm {OPT} -O(1)を満たすもの) $ビン)。例えば、
“ビン被覆のためのより良い近似アルゴリズム”、Csirik、Johnson、Kenyon、SODA 2001、または “bin
coveringのための漸近完全多項式時間近似スキーム”、Jansen and Solis-Oba、TCS 2003。

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です