# Algorithms for stacking gage blocks

I'm looking for algorithms for stacking gage blocks.

For those unaware, gage blocks are used in machine shops for measuring with high precision and come in sets something like this...

Mitutoyo's 56 block metric set

 1 0.5mm block
9 blocks from  1.001mm to   1.009mm in steps of 0.001mm
9 blocks from  1.01mm  to   1.09mm in steps of  0.01mm
9 blocks from  1.1mm   to   1.9mm in steps of   0.1mm
24 blocks from  1.0mm   to  24.0mm in steps of   1.0mm
4 blocks from 25.0mm   to 100.0mm in steps of  25.0mm


And the way machinists generally stack these is to start at the least significant digit and work your way left, for example...

Target size: 28.538mm


For any given set of N distinctly sized gage blocks there are 2^N stacks that can be made as the order of blocks in the stack isn't important. This number of combinations is certainly too high to brute force.

So given a set of gage blocks and a valid target size, the algorithm should be able to select a set of gage blocks that add up to the target size.

I would like to see what algorithms people can come up with to solve this problem, so far I've only come up with...

Use A* with stacks being the nodes, block additions being the edges and counting the number of correct consecutive digits from the right as the heuristic.

• What would be the input and the output of your algorithm? Please be precise, it is unclear what you are asking for. Commented Mar 29 at 12:04
• Sorry, Given a set of gage blocks and a valid target size, the algorithm should be able to select a set of gage blocks that add up to the target size. Commented Mar 29 at 12:07