4

This is an abstract computer code application that I'm trying to solve, but I think the following real life example kind of helps to illustrate the type of problem I'm working with.

In this example, the first group contains railroad passenger cars. Each object (a passenger car) in this group has 2 properties: weight, and length.

The second group contains railroad cattle cars. Each object in this group also has the same 2 properties: weight, and length.

The third group might contain luggage cars, and all have the weight and length properties.

etc. etc... (there need to be 7 groups total, but I think you get the idea).

The weight and length for each car in each group can be different.

Now, there is a locomotive, which can pull 7 cars, and 1 car must come from each group. Moreover, the combined weight of the 7 cars cannot exceed x, and the combined length of the 7 cars cannot exceed y.

What's the mathematical process for determining which 7 cars will get as close to the weight and length limits as possible without exceeding them?

Timothy
  • 41
  • 4
    This seems related to the knapsack problem. Definitely not the same, but i wouldn't be surpised if the problem was NP-complete. https://en.wikipedia.org/wiki/Knapsack_problem. – Thomas Andrews Jul 04 '13 at 03:01
  • You will find information by googling multiprocessor scheduling and/or bin packing. – André Nicolas Jul 04 '13 at 03:02
  • What is your goal? Sure, you want to get both parameters as close as possible. But, which do you value more--the weight or the length parameter? – apnorton Jul 04 '13 at 03:05
  • For the sake of this example, let weight be the most important. The train should be pulling as close to its maximum weight limit as possible. – Timothy Jul 04 '13 at 03:07
  • 1
    We get many requests like this. You are asking for a mathematical solution to a problem without defining what is valued in the hope that mathematics can provide an optimum. Unfortunately, optimum in this sense is not a mathematical concept. If the objective is well defined, we can help. Your last comment helps a lot-the objective function is maximize weight pulled and within that maximize length. Now the problem is well defined. A brute force search can solve it in $n^2$ time-loop over p cars, for each loop over c cars, find max l cars and measure the optimum. Sort and you are done. – Ross Millikan Jul 04 '13 at 03:34
  • @RossMillikan, thanks, it looks like I have to resort to brute force. I was hoping for something less computationally intensive, but I guess I'm out of luck. – Timothy Jul 04 '13 at 18:51

0 Answers0