# Relations between the knapsack problem, the bin packing problem, and the set packing problem?

I wonder what relations are between the knapsack problem, the bin packing problem and the set packing problem?

From their mathematical formulations, I don't see the first two belong to the third one i.e. the set packing problem, although I feel the third one sounds more general than the other two.

Or under what conditions there are some conversions between each other?

Thanks!

• Aren't these all NP-complete? All NP-complete problems can be converted to eachother in polynomial time. See wp:Karp's_21_NP-complete_problems. – Realz Slaw Oct 31 '12 at 14:44
• @Realz_Slaw: Thanks! Your point from polynomial reduction is correct. I was asking about relations and conversions at the level of problem formulations. Or are these two points of view the same? – Tim Oct 31 '12 at 14:47
• Well you could be asking for a more direct conversion, and/or a human explanation about their relationship, as the reductions given for one NP-complete problem to another can be multi-step (conversion to multiple intermediate problems) and lose a lot of easily "explainable" information. Or you could be asking something I simply don't understand. – Realz Slaw Oct 31 '12 at 14:53
• Are you asking about "one-one reduction"? – Reza Feb 1 '13 at 3:29
• @Reza: it can be that or any others. – Tim Feb 1 '13 at 3:38