HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Stacking things of different thickness to approximate desired thickness

Submitted by: @import:stackexchange-cs··
0
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

Context

StackExchange Computer Science Q#106766, answer score: 2

Revisions (0)

No revisions yet.