Packing differently sized chunks of data into multiple bins
Posted
by
knizz
on Stack Overflow
See other posts from Stack Overflow
or by knizz
Published on 2010-12-23T18:24:12Z
Indexed on
2010/12/23
18:54 UTC
Read the original article
Hit count: 271
EDIT: It seems like this problem is called "Cutting stock problem"
I need an algorithm that gives me the (space-)optimal arrangement of chunks in bins. One way would be put the bigger chunks in first. But see how that algorithm fails in this example:
Chunks Bins
-----------------------------
AAA BBB CC DD ( ) ( )
Algorithm Result
-----------------------------
biggest first (AAABBB ) (CC )
optimal (AAACCDD) (BBB)
"Biggest first" can't fit in DD. Maybe it helps to build a table like this:
Size 1: ---
Size 2: CC, DD
Size 3: AAA, BBB
Size 4: CCDD
Size 5: AAACC, AAADD, BBBCC, BBBDD
Size 6: AAABBB
Size 7: AAACCDD, BBBCCDD
Size 8: AAABBBCC, AAABBBDD
Size 10: AAABBBCCDD
© Stack Overflow or respective owner