# How do you load $n$ cannisters into $m$ trucks such that no truck is overloaded

We have $n$ cannisters, and for each one there is a specified subset of trucks which can carry it. There are $m$ trucks that can each hold $k$ cannisters. Is there a way to load all $n$ cannisters into the $m$ trucks so that no truck is overloaded, and each container goes into a truck that is allowed to carry it?

Is this problem NP-complete, or is it possible to solve it in polynomial time? Viscerally, I feel like there should be a polynomial time algorithm, but so far I haven't been able to come up with anything clever to solve it.

Alternatively, consider a variation of the problem where any cannister can go on any truck, but some cannisters can not be on the same truck together. Is there a way to load the $n$ cannisters on the $m$ trucks such that there are no conflicts with cannisters on some truck? Can we solve this problem in polynomial time?

This sounds like a variant of the knapsack problem so it is probably NP complete.

• Do you think the alternative problem is also NP-complete? – Cortney Nov 14 '14 at 6:34