🎙️ tryashtar · 0 points · Posted at 23:24:24 on October 13, 2016 · (Permalink)
Say you have a large collection of small blocks, and you need to arrange them in a perfect rectangular prism such that the volume is ≥ 217, for instance.
There are an infinite amount of ways to do this. You could do 1×1×217, or 10×10×3, or even 7382×2729×836.
Of course, using huge side lengths (lots of blocks in each dimension) would result in a huge prism, and the surface area would go up. Normally, to minimize surface area, you'd simply set each length to the cube root of the volume, but we're assembling this prism out of cubes, so only whole numbers are allowed.
In the case of 217, the optimal configuration is 9×5×5, with volume 225 and surface area 230. Note that, because our numbers are whole, it's not really very cube-ish. The smallest surface area whole-number cube with volume ≥ 217 is 7×7×7, but 9×5×5 beats it in the surface area department.
Is there a way to determine these lengths based on the volume? I've tried tons of different methods, and none of them always find the correct answer. If there's some formula or process that I can use to accomplish this, I would appreciate any help or insights. Thanks!
edderiofer · 2 points · Posted at 23:51:12 on October 13, 2016 · (Permalink)
This is an example of integer programming, which isn't easy.
🎙️ tryashtar · 1 points · Posted at 00:43:25 on October 14, 2016 · (Permalink)
Hm, I took a look at the Wikipedia page. It's not just hard, it's NP hard!
In a programming context, I wonder how it could be solved, or at least what possibilities should be checked. I can always iterate from one to volume for each dimension, but that creates tons and tons of unnecessary checks.
[deleted] · 2 points · Posted at 00:08:53 on October 14, 2016 · (Permalink)
There is not a formula, but the algorithm is simple enough:
If V is your volume and C is the smallest cube greater or equal to V, then you compute the minimal area for each possible volume between V and C, and you select the one which provides the smallest area.
To compute the minimal area given a volume X you simply chech all the ways in which X can be written as the product of 3 integers a <= b <= c.
The method is easy to implement and also fast if the volumes are small (say under 10000).
🎙️ tryashtar · 1 points · Posted at 01:01:00 on October 14, 2016 · (Permalink)*
Aha! That makes sense. It's guaranteed that there's at least one volume between V and C that can be written as a product of three factors (because C is by definition), so I guess then the (much easier) problem to grapple with is finding all the three-factor sets which produce the volume.
Anyway, thanks! That's very helpful.
EDIT: Goodness, finding all the three-factor sets which produce the volume when multiplied together is tougher than I thought!
[deleted] · 2 points · Posted at 06:10:28 on October 14, 2016 · (Permalink)
Actually, it is super-easy.
Assume you have X and you want to list all the triples (a,b,c) such that a * b * c = X and a <= b <= c (to avoid duplicates)
The last inequality implies that a3 <= X, so you loop on a from 1 up to the value such that a3 <= X.
Then, for each a, you check if X is divisible by a. If so, you need to decompose X/a into b * c. But again, you know that b2 <= X/a and moreover b >= a, so you loop on b from a to the value such that b2 <= X/a. For each such b, you check if b divides X/a. If so, your numbers are (a, X/a, X/a/b).
Implementing all this in any programming language does not take more than 5 minutes.
But if you have difficulties in programming, this is not the right subreddit.
🎙️ tryashtar · 1 points · Posted at 13:24:10 on October 14, 2016 · (Permalink)
Thank you. I was really more interested in understanding the math, so if I decide to program it to test the method, I can work out the implementation details myself if I understand the math. Your comments have been very helpful.