patternMinor
Stacking things of different thickness to approximate desired thickness
Viewed 0 times
approximatethingsdesireddifferentthicknessstacking
Problem
I have $N$ objects of different thickness. Is there an algorithm to determine which of those objects should be stacked on each other to get as near to a desired thickness as possible? (I don't want to numerically check every combination.)
Solution
This is as hard as the subset sum problem. The subset problem asks "is there a way to get exactly the desired thickness?". Obviously, if we could solve your problem, we could also solve the subset sum problem. Unfortunately, the subset sum problem is NP-hard, so your problem will be too.
In practice you can try using an approximation algorithm for the subset sum problem, e.g., by rounding to the nearest integer (or to the nearest multiple of $1/k$ for some $k$) and then applying the dynamic programming algorithm for subset sum. See, e.g., https://en.wikipedia.org/wiki/Subset_sum_problem
In practice you can try using an approximation algorithm for the subset sum problem, e.g., by rounding to the nearest integer (or to the nearest multiple of $1/k$ for some $k$) and then applying the dynamic programming algorithm for subset sum. See, e.g., https://en.wikipedia.org/wiki/Subset_sum_problem
Context
StackExchange Computer Science Q#106766, answer score: 2
Revisions (0)
No revisions yet.