I'm studying Bin Packing Problem for my thesis and I meet this definition of the decision verson of the problem in the book "Computers and Intractability" by Michael R. Garey and David S. Johnson:
INSTANCE: Finite set $U$ of items, a size $s(u) \in Z$ for each $u \in U$, a positive integer bin capacity $B$, and a positive integer $K$.
QUESTION: Is there a partition of $U$ into disjoint sets $U_1, U_2, ..., U_k$ such that the sum of sizes of the items in each $U_i$ is $B$ or less.
And there is a curious comment about its solution in polynomial time, that is "Solvable in polynomial time for any fixed $B$ by exhaustive search."
Now my question is how it is possibile, searching in internet I've found nothing but this question: NP-hardness of bin packing problem for fixed bin size but the answer doesn't convinces me, it seems wrong, or maybe simply I don't understand it. Can you help me with this?
With a fixed bin size you also have a fixed number of possible ways to (partially) fill a bin. Suppose there are $p$ ways to do that.
If you solve each of the $k$ bins separately, you'd get $p$ possibilities for each bin, and then $p^k$ possibilities alltogether. This is exponential, and not what we would like. Note that many of those possibilities will not match up with the actual item sizes you have available, so it is merely an upper bound.
Instead of assigning a partition to each bin, you can do the opposite - assign some number of bins (possibly zero) to each partition. You then have $(k+1)^p$ possible ways of that assignment. This has a fixed exponent, so is polynomial in the number of bins. The degree $p$ of this polynomial can be huge, and this also is an upper bound since most of those assignments will have the wrong total number of bins, but all that does not matter - it is enough to show that it is polynomial.
For example, suppose the bin size is $3$. There are only $6$ possible ways to partially or completely fill up a bin: $1$, $1+1$, $1+1+1$, $2$, $2+1$, $3$. Let $a,b,c,d,e,f$ be variables representing how many bins there are for each of those ways of filling them. Each variable must have an integer value from $0$ to $k$ inclusive. So there are no more than $(k+1)^6$ possibilities to check. In fact, there are far less, since we also have $a+b+c+d+e+f=k$. For example, suppose we want to check if $a=b=c=d=0$, $e=f=4$ is a valid bin packing. We have four bins that contain a size $2$ and a size $1$ item, and four bins with a size $3$ item. If your inventory $U$ contains four items of each size, you have a valid packing. However many bins of size $3$ you have, there are only $6$ variables that you need to determine, and that is polynomial in the number of bins.