Hello! Since I don't really know the solution of this problem this might be posted in the wrong forum, sorry if that's the case.
My problem is this; I have pipes in different lengths, let's say 2, 5 and 8 meters each. Now I am going to connect x pipes of each length so that I get a total length of 28 meters. I want to do this in a way that I get minimum overhead, second I want to use as many long pipes as possible.
The answer of my example is easy to calculate "in head", 3*8 and 2*2 pipes, but if there are 9 different pipe lengths and a total length of 155337 meters?
Can someone please help with an algoritm that I can use to calculate different pipes and lengths and an easy-to-understand explanation how it works? Thanks in advance!
Thanks for reply!
I have written a small program in Excel (VBA) that test all possible combinations, one in a time. But when there are 4 or more pipe lengths unfortunately it gets really, really slow (and there will be nestled loops in absurdum).
What about four or five pipe lengths? Is this calculateble:
... where 2, 5, 10 and 25 is pipe lengths and I want as many "d" and as few "a" as possible?
It's a knap-sack like problem, a solution can in principle be found by exhastive search. But the general problem is NP-complete (which for all practical purposes means that the required computaional time for all known algorithms grows exponentially with problem size, and so only small problems can be solved)
Having said that, of course if the available pipe lengths satisfy some convienient conditions which in practice often occur(for example if a is the shortest pipe length and the others are 2a, 4a, 8a) the greedy algorithm will be optimal.
.
Unfortunately, that's not the case. Well, seems like this problem is more tricky than I excpected, still you ppl have learn med what a "Diophantine equation" is and for that I thank you - very intresting! I didn't like math at all back in school, but now when I got older I start to enjoy math and it's beauty... hopefully it's never to late to learn, though I probably won't be an expert in this subject.
Thanks for your time!