Bin Packing 問題　と　weight の工夫

今回の演習では、weight を工夫した Best-First 探索により Bin Packing 問題を解こうとしている。

First Fit Algorithm のアイデアを借りて　weight　を作るとする。

ビンの水の総和を weight として使うのはどうだろう？

コップの状態 ビンの状態 weight
コップの容積 4 3
水の入ったコップの数 4 8
ビンの番号 1 2 3 4
水の総和 0 0 0 0
0
コップの容積 4 3
水の入ったコップの数 3 8
ビンの番号 1 2 3 4
水の総和 4 0 0 0
4
コップの容積 4 3
水の入ったコップの数 2 8
ビンの番号 1 2 3 4
水の総和 8 0 0 0
8
コップの容積 4 3
水の入ったコップの数 1 8
ビンの番号 1 2 3 4
水の総和 8 4 0 0
12
コップの容積 4 3
水の入ったコップの数 0 8
ビンの番号 1 2 3 4
水の総和 8 8 0 0
16
コップの容積 4 3
水の入ったコップの数 0 7
ビンの番号 1 2 3 4
水の総和 8 8 3 0
19
:
:
 　
コップの容積 4 3
水の入ったコップの数 0 2
ビンの番号 1 2 3 4
水の総和 8 8 9 9
34
コップの容積 4 3
水の入ったコップの数 0 0
ビンの番号 1 2 3 4
水の総和 10 10 10 10
40