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$).