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?

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.