Given an elevator with max weight and n people with x_i weights, find out minimum number of rides 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 this looks very similar to a dynamic programming coin change/knapsack problem, however it is not coin change (which would be asking for the fewest number of weights to make an exact amount), and it is not knapsack (the weights do not have values and it's like I can have more than 1 knapsack).

Is there a common name/solution for this problem?

Butyraceous

Looks to me this is simply bin packing – Spinet

Answer 1

This is actually a (1D) Bin Packing problem:

In the bin packing problem, objects of different volumes must be packed into a finite number of bins or containers each of volume V in a way that minimizes the number of bins used. In computational complexity theory, it is a combinatorial NP-hard problem.

Here the persons map on the objects en the bins on the rides. Like the bin packing problem we want to minimize the number of rides "used" and each person occupies a certain "volume" (that person's weight).

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

The paper A New Algorithm for Optimal Bin Packing by Richard E. Korf discusses an algorithm to solve this problem exactly. It works by using a heuristic approach first and calculating a lower bound, and then use branch and bound to iteratively derive a better solution than the heuristic one until the lower bound is reached, or no solution can be found anymore.

Spinet

Answer 2

Please correct me if I'm wrong (not the most efficient), but I think you could put all the weights into a max heap, and then use a greedy algorithm to pick the sets.

Amish

yep, assuming order of individuals doesn't make a difference, (who arrived to the elevator first), then I have to agree with Sritej, this looks like a greedy algorithm to me ... and I believe it is the most efficient too – Punchball

Suppose the weight limit is 7, and the people weigh [3, 3, 2, 2, 2, 2]. Then the optimal answer is 2, but your algorithm gives 3. – Valeric

@Valeric You're absolutely right. Greedy algorithms fail a lot of the time because of those types of cases =/ – Amish

Answer 3

You're on the right track. The problem is solved by a modified coin-change algorithm: rather than demanding an exact solution, you find the one that attains the highest total without exceeding the target amount. Of course, if you find a solution whose shortfall is less than any remaining set element, you stop and report that solution.

When you find a solution, remove the "used" weights and iterate until you have allocated them all. The number of iterations is the quantity of elevators you need.

If you sort the elements in descending order, this gives you a "greedy" beginning with backtracking. I suspect that this is reasonably close to optimal for many cases, especially if you memoize the results so that you don't repeat mistakes on the next iteration.

You might try some pathological cases, such as a limit of 100, and extreme weights like

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

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

Does that move you toward a solution?

Polyanthus

This can give the wrong answer in some cases. Suppose the weight limit is 14, and the people weigh [10, 6, 6, 6, 6, 3, 2, 2]. Then the correct answer is 3 (10+3, 6+6+2, 6+6+2), but your approach can give 4 (10+2+2, 6+6, 6+6, 3). – Valeric

Nice test! This will give the wrong answer in that case. The problem comes just as you constructed it: when those small values are critical to finding more "middle-value" maximal solutions than the "biggest first" ordering will get. – Polyanthus