Given the elevator with maximum weight and n people with x_i weights, find out the minimum number of trips needed

Question

input: max_weight = 550 n = 4 x_i = [120, 175, 250, 150] output: 2 // [[250, 175, 120], [150]] 

My initial impression is that it looks very much like a coin change / change problem with dynamic programming, however it is not a coin change (which will request the least amount of weights to get the exact amount), and it’s not like a backpack (the scales do not have values, and it looks like I can have more than 1 backpack).

Is there a common name / solution for this problem?

Answer 1

This is actually a (1D) bin packing problem :

In the problem of packing a basket, objects of different volumes must be packed in a finite number of containers or containers in volume V so as to minimize the number of bins used . In computational complexity theory, this is a combinatorial NP-hard problem.

Here, people display objects in bunkers on attractions. Like the problem of packing a basket, we want to minimize the number of "used" attractions, and each person occupies a certain "volume" (this weight).

The problem with packing the box - as stated in the article - NP-hard. We can use dynamic programming (but it still has the worst case - exponential time).

Article A new algorithm for optimal bin packing by Richard E. Corf discusses an algorithm to solve this problem exactly. It works using a heuristic approach and calculates the lower bound, and then uses the branch and is bound to iteratively output a better solution than the heuristic, until a lower bound is reached, or no solution is found.

Answer 2

Please correct me if I am wrong (not the most efficient), but I think you could put all the weights in the max heap , and then use the greedy algorithm to select the sets.

Answer 3

You are on the right track. The problem is solved using a modified coin replacement algorithm: instead of requiring an exact solution, you will find one that reaches the highest total amount that does not exceed the target amount. Of course, if you find a solution whose deficit is less than any remaining set element, you stop it and report the solution.

When you find a solution, remove the “used” weights and repeat them until you select them. The number of iterations is the number of elevators you need.

If you sort the items in descending order, this gives you a greedy start with a retreat. I suspect this is close enough to optimal for many cases, especially if you memoize the results so that you don't repeat the errors in the next iteration.

You can try some pathological cases, such as the limit of 100, and extreme weights, such as

 [93, 91, ..., 5, 4, 4] 

The "greedy" algorithm first goes to 93 + 5, but later settles to 91 + 4 + 4 (a closer solution). This is where memoization comes in handy.

Will this lead you to a decision?