0
$\begingroup$

I have a problem that could be a variant of "bin packing problem".

  1. Input: Given $N$ identical items: $i_1, i_2, ...,i_N$ with the same weight (or volume). Given $M$ bins: $b_1, b_2, ..., b_M$ with the same capacity $K$. Each bin has already contained a number of items: $k_1, k_2, ..., k_M$ in which $k_i <= K$. ($k_i = K$ means the bin $i$ is full).
  2. Output: The allocation solution of placing $N$ items to $M$ bins that maximize the number of full bins. Is there any polynomial algorithm for this problem?

The same question but in the general case that items have different weights (or volumes): $w_1, w_2, ..., w_N$. The value $k_i$ of the bin $i$ is the total weight of the current inside items. And the bin is full when it contains enough items that the total weight above $95$% capacity ($k_i \ge 0.95 K$).

$\endgroup$
5
  • $\begingroup$ Presumably your list should end at $b_M$ rather than $b_N$. Similarly for k. $\endgroup$
    – Blitzer
    Jun 11, 2021 at 11:23
  • $\begingroup$ Does the 95% definition of full apply to the specific problem, or only to the general one? $\endgroup$
    – Blitzer
    Jun 11, 2021 at 11:24
  • $\begingroup$ Are the weights to be treated as real numbers, or to some specified precision? $\endgroup$
    – Blitzer
    Jun 11, 2021 at 11:25
  • $\begingroup$ When you same "number of items", I guess you mean "weight". $\endgroup$
    – Blitzer
    Jun 11, 2021 at 11:26
  • $\begingroup$ @Blitzer: You are right, I corrected it to bM and kM. The 95% definition is just for a specific problem, we can use another value. The weights are the real number. $\endgroup$
    – D.D. Lam
    Jun 12, 2021 at 2:07

1 Answer 1

Reset to default
0
$\begingroup$

For each bin, define $n_i$ as the minimum number of items required to fill the bin - ie to get it to 95% full. Note that for some values of $k_i$ this may not be possible, so ignore those bins.

We now have a set of $n_i$ and we want a subset of them such that we have as many as possible with the total $=N$.Obviously we'll prefer smaller $n_i$s. Can we just pick the smallest ones until we get to $N$? I think we can. Done.

$\endgroup$
1
  • 1
    $\begingroup$ Your answer is great! That is much simpler than I thought. $\endgroup$
    – D.D. Lam
    Jun 14, 2021 at 2:29

You must log in to answer this question.

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