0
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.