algorithmdynamic-programmingbacktrackingknapsack-problemcoin-change# Given an elevator with max weight and n people with x_i weights, find out minimum number of rides needed

```
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?

Solution

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

In the bin packing problem,

objects of different volumesmust be packed into a finite number of bins orcontainers each of volumein a way thatVminimizes 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.

- Facebook warm up challenge that I can't seem to figure out - Battleship
- For given sequences, build graph which will contain path for each sequence
- Print 2-D Array in clockwise expanding spiral from center
- Cartesian product of multiple arrays in JavaScript
- How can I optimize the algorithm to find the longest common subsequence (LCS) between two strings?
- Fill pattern of an arbitrary size in Intel hex file
- Efficiently create random sample from expand.grid output without using expand.grid
- How do I select a combination of two variables from a dataframe when each variable value can only be selected once?
- Heuristic function for water jug problem in A* search
- match all subitems in a string as different matches with regexp
- Check if all elements in a list are identical
- Time limit exceeded on the code: Check If a String Contains All Binary Codes of Size K
- Dynamic Programming - Minimum number of coins in C
- Simple script to find "lowest" available domain name
- How to get Floyd's triangle in JAVA with descending numbers
- Rearrange groups without repeating subjects
- how to calculate binary search complexity
- Find the maximum depth of a set of intervals
- Can a binary search tree be constructed from only the inorder traversal?
- Time complexity of StringBuilder reverse method
- Recommendation algorithm (and implementation) for finding similar items and users
- Get every combination of bits for two binary numbers
- The simplest algorithm for poker hand evaluation
- How to replace all occurrences of a character in string?
- Reverse integer bitwise without using loop
- Equal sides of an array in JS
- Why does BIDE use the semi-maximum period for search space pruning?
- C++ ICP Algorithm Memory Leak
- Looking to identify a "classic" problem and identify availble algorithms to solve it
- Algorithm to find true value range in bool array