ビンパッキング問題
8台の新車をトラックで移動する。新車の重量はそれぞれ100キログラム単位で 33, 61, 58, 41, 50, 21, 60, 64 である。各トラックが、12,000 kg の重量まで運べるとき、全ての新車を一度に移動させるのに必要とされるトラックの最小数は、いくつであるか考える。まず、トラックを容量120のビンとし、新車は、そのビンに詰める荷物とする。具体的に調べることによって必要な箱の最小数を見つけることができるが、ここでは決められた手順(アルゴリズム)を使って解いていく。2つのアルゴリズムを紹介する。
アルゴリズムA
荷物を空いている容量が最大のビンに詰める。
どのビンにも荷物が入らないとき、新しいビンに詰める。
この方法だと、ビンは5個(つまりトラック5台)必要となる。
アルゴリズムB
荷物を空いている容量が最小のビンに詰める。
どのビンにも荷物が入らないとき、新しいビンに詰める。
この方法だと、必要なビンは4個(トラック4台)である。
2つを比べるとAよりもBの方が良いアルゴリズムである。実際にはもっと優良なアルゴリズムがあるかもしれない。