0
$\begingroup$

I'm slightly embarrassed to ask this question as I feel that the answer might be exceedingly simple but I sat down to think about it and can't seem come up with a formula.

I have a fixed number of bins and a variable number of items. How many total bins will I need to fit n number of items.

Example: 3 bins of capacity 3 and 5 items. How many bins are needed to fit 5 items? Obviously the answer is 2. 1 bin will be full and the other will have 1 empty slot.

What is the formula for this?

The information I need to know is:

  1. How many completely empty bins will remain?
  2. How many empty slots will remain in the partially full bin?

NOTE: I know the number of items will never exceed the capacity of all the bins combined.

$\endgroup$
1
  • $\begingroup$ It is just division with remainder. Divide the number of items by the capacity of a bin. If the items are of different sizes, it is much harder. Bin packing is NP-hard $\endgroup$ Aug 31, 2020 at 22:09

1 Answer 1

2
$\begingroup$

One answer will involve a couple of functions you may not be familiar with: floor and modulo.

They're simple enough, though. The floor of $x$, denoted $\lfloor x \rfloor$, is simply the largest integer not greater than $x$. Broadly speaking, you just round down. So $\lfloor 3.14 \rfloor = 3, \lfloor 6 \rfloor = 6, \lfloor -2.72 \rfloor = -3$, and so forth.

Then $a$ modulo $b$, written $a \bmod b$, tells you the remainder after $a$ is divided by $b$. So, for example, $8 \bmod 5 = 3, 27 \bmod 4 = 3, 6 \bmod 3 = 0$, and so on.

OK, with that out of the way, suppose you have $b$ bins with capacity $c$ each, and you have $n$ items to put in the bins. Assuming the number of bins is in fact enough to hold the items, the answers are

  1. The number of empty bins is $\left\lfloor \frac{bc-n}{c} \right\rfloor$.

  2. The number of empty slots in the partially full bin is $bc-n \bmod c$.


For example, let's say you have $7$ bins, each capable of holding $5$ items. You have $22$ items. Then $b = 7, c = 5, n = 22$. That means

  1. The number of empty bins is $\left\lfloor \frac{7\times5-22}{5} \right\rfloor = \left\lfloor \frac{13}{5} \right\rfloor = 2$.

  2. The number of empty slots in the partially full bin is $7 \times 5 - 22 \bmod 5 = 13 \bmod 5 = 3$.

If this last result is $0$, that simply means there are no partially full bins.

$\endgroup$
1
  • $\begingroup$ Brian, you're a life saver! My initial thought in the first 2 seconds was take the modulus but whatever I was doing wasn't working out and what I thought was a very simple question was making my brain explode. $\endgroup$ Aug 31, 2020 at 22:30

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .