Bin Packing 問題　データ構造

各 Node の表現について

例題

コップの容積　（同じ容積のコップが複数ある） ビンの容積 ビンの数
4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3 10 4

Node 数をいたずらに増やしてしまう、あまり上手でない表現方法

Node =　コップの状態＋ビンの状態

コップの状態

コップの番号 1 2 3 4 5 6 7 8 9 10 11 12
コップの容積 4 4 4 4 3 3 3 3 3 3 3 3
水を注いだビン 1 - 1 - 2 2 3 3 4 - 4 -

ビンの状態 A

ビンの番号 1 2 3 4
ビンに水を入れたコップの番号 1 3 5 6 7 8 9 11
ビン中の水の総和 8 6 6 6

ビンの状態B

ビンの番号 1 2 3 4
ビンに水を入れたコップの番号 7 8 1 3 5 6 9 11
ビン中の水の総和 6 8 6 6

ビンを番号で区別することは無意味に状態の数を増やす。
状態 A と状態 B は同一視したい。

Node 数を減らす表現方法

コップの状態 ビンの状態
コップの容積 4 3
水の入ったコップの数 4 8
ビンの番号 1 2 3 4
水の総和 0 0 0 0
コップの容積 4 3
水の入ったコップの数 3 8
ビンの番号 1 2 3 4
水の総和 4 0 0 0
コップの容積 4 3
水の入ったコップの数 2 4
ビンの番号 1 2 3 4
水の総和 8 6 6 6

水の総和が大きい順にビン番号を並べる