[Cenron]

So I am trying to put together a parts ordering calculator for work, and I am trying to figure out what the best to get what parts to order based on the length of the unit and the length of the parts.

So for example I have a counter that is 600 inches long, and I have 3 type of railings that we would use. The first one is 17 inches, the next one is 14 inches and the last one is 11 inches.

The idea is figuring out how many ( Combination of the 3 ) of the 17, 14 or 11 inch railings does would it take to meet the 600 inches. If it ends up going over, then we can cut it size, but I want to get as close as possible.

So in this situation if the counter is 634 inches, then we would order:

35x 17"
2x 14"
1x 11"

So I would have to write an algorithm i guess to get the best combination of the 3 length of railing to fit the counter with as little excess as possible. Anyone have any ideas on how to achieve this? I don't really have any idea in what direction to go, for the solution. I dont know if it's as easy as getting a formula and plugging in the numbers, or does there need to be a little bit more logic to it?

[Skydiver]

Do searches for "unbounded knapsack problem" and "bin packing problem". There are several algorithms proposed to solve those classes of problems.

I don't think this question is C/C++ specific so I'm going to move this question under Computer Science.

[macosxnerd101]

I'd use an Integer-Linear Program formulation and then feed this to an ILP solver. I think MATLAB has one built in. You could possibly find one online. You could also try a cutting plane or branch and bound algorithm by hand. I'd probably try branch and bound first.

Here is the formulation:
min 17x_{1} + 14x_{2} + 11x_{3} - 600 s.t.
x_{1} + x_{2} + x_{3} >= 600 (better to buy too much than too little)
x_{1}, x_{2}, x_{3} \in Z^{+} (you are buying integer amounts of these goods)

To solve using branch-and-bound, you solve the LP relaxation. Then you pick a non-integer variable and round it up and down. Then given each of these fixed cases, solve the LP relaxation for the remaining variables. Repeat until all are integers and pick the best.

[Skydiver]

If you have Excel, the Excel Solver feature also does linear programming.

Out of curiosity, is there also a minimum length constraint? For example if you do a come up with a solution where you are just 1" short of the target length, is that 1" that you cut off from the extra 11" that is ordered even usable? I'm asking because don't you need to cut threads into that piece to be able to screw it into a junction piece. What if the junction piece is more than 1" long?