Bin Packing 問題 近似アルゴリズムBin Packing 問題 近似アルゴリズム ■ Bin Packing 問題は次のように定義される： いろいろな大きさのコップに、その容積一杯に水が入っているとする。各コップ u の容積は正の整数 s(u) とするとき、コップの集合を U とする。 一方、容積がどれも正の整数 B であるビンが K 個あるとする。 各コップの水はどれか一つのビンに注ぐとするとき、各ビンがこぼれないように注ぐ方法はあるか？ このように、方法が存在するか否かを問う問題は、「決定問題」と呼ばれる。 ■ 一方、次の問題を「最適化問題」と呼ぶ。 コップの集合Uに対して、最小何個のビンがあれば、各ビンがこぼれないようにできるか？ 最適化問題を解いて、最小のビンの数が OPT 個と分かったならば、決定問題は OPT ≦ K ならば、方法が存在し、 K ＜ OPT ならば、方法は存在しない というように簡単に解くこと
