0
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ What would be the input and the output of your algorithm? Please be precise, it is unclear what you are asking for. $\endgroup$
    – Nathaniel
    Mar 29 at 12:04
  • $\begingroup$ 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. $\endgroup$ Mar 29 at 12:07

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.