Is the following problem polynomial ? Or NP-Complete ?
Problem: Bin packing with 2 types of objects.
Input: $C$, the capacity of each bin, $N_a, N_b$ the numbers of objects $a$ and $b$, $w_a,w_b$ the weight of the objects, $k$, the maximum number of bins.
Output: Yes if all objects fit in the $k$ bins without exceeding the capacity of any bin or cutting objects, No otherwise
My first intuition was that with only two types of objects, there must be less solution and maybe enumeration is polynomial, so I tried count them.
For an instance of size $n$ (with $n$ objects), we can encode solutions as $n$-tuples $[0,1,1...,0,1]$ (the first objects being in the first bin until it's full, then the second, etc). For instances of size $n$, there are $2^n$ distinct solutions. Since there are $n$ instances of size $n$ (I mean, $n$ pairs $(N_a,N_b)$ such that $N_a+N_b=n$), and by the pigeonhole principle, there must be an instance with at least $2^n/n$ solutions. So a simple enumeration of solutions doesn't work.
Then, I started thinking that the problem may be NP-Complete. Reducing a graph problem seems no to be a good idea: graphs are big structures, and this problem as only a few numbers as an input. At this point, I realized that all the NP-Complete problems I've heard of had biggers inputs.
Now, I'm a bit confused. I can't figure out a good algorithm or a reduction.
