0
\$\begingroup\$

Imagine you have a room X metres long. You have different parts P of diverse lenghts L and importances I. However, the quantity Q of each part is limited and different. You want to fit in as many of these parts as possible while also prioritizing those with higher importances. ¿How do you do it?

I've been trying to find a better way to resolve this than testing all combinations, but without success. ¿Any suggestions? (And by the way, if this kind of problem has a name, please post it as a comment or a reply)

Example:

Lenth of room: 5m
Number of parts: 4
Part data:

Part 1: 0.75m, 1 Units, 2 Importance
Part 2: 1m, 3 Unit, 0.75 Importance
Part 3: 0.47m, 4 Units, 1 Importance
Part 4: 1.33m, 2 Units, 3 Importance

Now as X, P, L, Q:
X = 5;
P.Lenght = 4;

P0.L = 0.75;
P0.Q = 1;
P0.I = 2;

P1.L = 1;
P1.Q = 3;
P1.I = 0.75;

P2.L = 0.47;
P2.Q = 4;
P2.I = 1;

P3.L = 1.33;
P3.Q = 2;
P3.I = 3;

Improve this question
\$\endgroup\$
1
  • 1
    \$\begingroup\$ This is variation of NP-complete problem called "knapsack packing". (algorithm with polynomial time does not exist). I am sure finding solution wont be problem when you know the name now :) \$\endgroup\$
    – wondra
    Jan 26, 2015 at 19:34

1 Answer 1

Reset to default
0
\$\begingroup\$

One thing you didn't specify clearly: What is the measure of success?

  • Number of Pieces?
  • Total importance?
  • Something else?

For so few pieces, an exhaustive search ("testing all combinations") is perfectly reasonable. Out of those 10 pieces, there's only a few hundred unique combinations to try.

I'll assume "Total importance" for now...

But more generally, these kind of optimization problems have many approaches, including advanced & exotic ones. Some easy ones include:

"Greedy" algorithm -- start with the best "bang for buck" piece (highest importance / length), and use them up first. Then go to the next.

Randomly iterate -- fill all your spots at random. Then, for a while, choose changes randomly (like swapping one piece for another that also fits) and if it makes the solution "better", keep it. Else, go back to the old one.

"Simulated annealing" -- like random iterations, but you start making "big random changes" and taper it down to smaller and smaller changes.

For the exact problem as written Greedy algorithm or Exhaustive search is probably sufficient.

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ You want to fit in as many of these parts as possible while also prioritizing those with higher importances The measure of success would then be usedLenght/totalImportance, right? If this is unclear in the sentence I've quoted, please tell me what the correct frasing would be so I can correct it. \$\endgroup\$
    – AvidScifiReader
    Jan 26, 2015 at 19:29
  • \$\begingroup\$ When your boss says, "Do this and also do that", it can be challenging to "win". :-) What you need is an arithmetic formula that you can apply to two proposed solutions to compare them. If it's "Used Length / Total Importance", then I would choose to use only one piece, whichever is best. (Because using two of that piece wont improve the score, and adding a "less good" piece would bring the score down.) Specifying the exact formula used will influence the result. \$\endgroup\$
    – david van brink
    Jan 26, 2015 at 19:34

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .