1
$\begingroup$

I have got some equipment of standard lengths, say:

equipment_lengths = {60, 48, 36, 29}

that I have to place on a given length of, say 100. I have to place this equipment so as to minimize material waste while covering the given length. I am allowed to exceed the given length of 100 but keep the excess minimized. I am not allowed to drop short of the given length. Also I have an unlimited number of each equipment.

So, one solution to the above example would be:

{60, 48} (excess = 60 + 48 - 100 = 8)

Another could be

{60, 60} (excess = 60 + 60 - 100 = 20)

The first solution is preferable to the second one as it minimizes the excess.

My first approach has been to implement a greedy algorithm that takes the longest equipment and keeps placing those till I exceed the given length. Once that happens I remove the last equipment I placed and place the next smaller ones till I exceed again. In the end I select the combination with the least amount of excess. For example the algorithm will successively do the following:

  • 60, 60 (excess = 20)
  • 60, 48 (excess = 8)
  • 60, 36, 36 (excess = 32)
  • 60, 36, 29 (excess = 25)

So, now it will select {60, 48} as the optimal solution when you remove last one equipment on excess. The algorithm then repeats the exercise by removing the last two equipments and finds another optimal solution. Finally it chooses the best one among the two optimal solutions it found.

Now, I have been studying bin packing and knapsack problem variations and while these problems look similar, I haven't been able to apply them to my problem. Does my problem have a well known solution? If not, how should I go about it to efficiently find the globally optimum solution?

Additional information: I think giving preference to longer equipments should be a good idea as the equipments need to be joined with screws or bolts so joining two longer equipments would be less work than three shorter ones, but I don't think it's more important than material wastage.

$\endgroup$
2
$\begingroup$

Your problem is NP-hard. The decision problem version of your problem is to ask whether there exists a selection of equipment achieving an excess of $e$ or less (given $e$ as input, and all the lengths). The special case of $e=0$ is exactly the subset sum problem, which is NP-complete. Therefore, the decision version of your problem is NP-complete, so finding an optimal set of equipment is NP-hard. In other words, you cannot hope for a fully polynomial-time algorithm to solve this problem.

If the lengths are not too large, you can adapt the standard dynamic programming algorithm for subset sum to solve your problem as well. It applies almost directly: the dynamic programming algorithm tells you, for each integer $\ell$, whether there is a way to choose equipment whose lengths sum to exactly $\ell$. Now you can check whether there is a solution for $\ell=100$, $\ell=99$, $\ell=101$, $\ell=98$, $\ell=102$, etc. (in that order) and take the first solution you find. The running time will be tolerable if the desired length (e.g., 100) is not too large.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.