Hi cmaury,
I hope you find the following answer satisfying. If not, please
request a clarification before rating and I will do my best to explain
further.
There are several different heuristics for solving the bin-packing (or
in this case, lumber-cutting) problem, and while none of them can
guarantee optimal efficiency, there are several that can get us
reasonably close to an ideal solution.
The algormithm I will provide is the "first-fit-decreasing" algorithm,
which is well-suited to situations, such as this one, where you know
all the lengths that you will need to cut the lumber into beforehand.
The basic algorithm goes something like this.
0: Usually in this algorithm every "bin" (or piece of lumber) is the
same size. This condition is not a huge hurdle to overcome and I don't
think the fact that your already-available pieces of lumber are
different sizes will affect the outcome too much. But for the purposes
of introducing the algorithm, assume that you have a bunch of stock
lumber, all of the same length.
1: First, make a list of all the lengths that the lumber needs to be
cut into, from largest to smallest.
2: Now, on the first piece of stock lumber, mark off the length of the
first piece you need to cut.
3: Look at the second length on the list. Can this be cut out of the
remainder of the first piece of stock? If so, then mark that distance
off too. If not, mark this distance off on a second piece of stock
lumber.
4: Repeat this process for every length in your list. First see if it
fits in the remainder of the first piece of stock, then the second,
etc. When you get to a piece of stock that has enough space to "fit"
the new cut, mark off that new cut. When you are done with the list,
you will have marked off two or three or four cuts on most pieces of
lumber, and in such a way that short cuts are paired with long cuts
relatively efficiently.
An example:
Let's say we have a bunch of boards that are 15 inches long.
We need to cut the following lengths in inches: 10, 8, 8, 7, 7, 7, 5, 5, 4, 2, 2, 2
On the first board, we mark off 10 inches.
We can't mark off a further 8 inches on the first board, so we mark it
on the second board.
Likewise, we can't mark off 8 more inches on the first or second
board, so we mark it off on a third board.
We can't mark off a further 7 inches on the first board, but we -can-
on the second board.
etc.
At the end of the process, this is how our boards are being cut up:
10+5
8+7
8+7
7+5+2
4+2+2
In this case, we have one inch of unused lumber on the second to last
piece of stock, and seven inches of unused lumber on the last piece of
stock. However, we can be relatively assured that we are not using
many more boards than is strictly necessary to use.
In your case, I feel that the algorithm can be modified simply by
letting the first three pieces of lumber be of the size that you have
on hand, and letting the remaining pieces of lumber be of some
arbitrary stock length that you pick.
I hope you find this answer satisfying! If you are not satisfied or if
you are having trouble understanding the algorithm, please request a
clarification and I will do my best to resolve any issues.
Thanks,
smudgy.
Here is a web page describing a few different bin-packing algorithms:
http://www.york.cuny.edu/~malk/tidbits/tidbit-bin-packing.html
and another one describing the bin-packing problem in general:
http://mathworld.wolfram.com/Bin-PackingProblem.html
and a couple with java-based bin packing solvers:
http://www.cs.ucf.edu/courses/cop3930H.01/JavaExamples/binpack.BinPack.html
http://www1.minn.net/~dchristo/BinPacker/BinPacker.html
http://www.research.compaq.com/SRC/JCAT/jdk10/binpacking/index.html
(This last is a really nice animation showing the -exact- method that
the algorithm described above uses. Check the box marked "first fit
decreasing" before running the demo. Unfortunately you can't enter
your own object sizes in this demo.)
This page has some computer code for a bin-packing computer program.
I'm not sure what language it's in... visual basic? You might be able
to glean some information from the program if you're planning to write
your own software:
http://www.cs.arizona.edu/icon/oddsends/bpack/bpack.htm
Search method:
Google search <bin packing>
Google search <bin packing java> |