Algorithms for stacking gage blocks

Question

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
Add block:    1.008mm, 27.53mm remaining
Add block:    1.03mm,  26.5mm remaining
Add block:    1.5mm,   25.0mm remaining
Add block:   25.0mm,    0.0mm remaining

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.

Answer 1

If you are looking for the sum of the blocks to be below the target size, you are talking about the 0/1 Knapsack problem. In your case, it seems that all profits are unit values.

Alternatively, if you are looking for the sum of the blocks to exactly add up to the target size, you are talking about the subset-sum problem.

Both of these are old classical problems, and plenty of efficient solutions have been studied in the literature.