I have a problem that could be a variant of "bin packing problem".
- 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).
- 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$).
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.