NP-completeness seems to me like one of those things that's mostly just theoretical and not really something you'd run into in a normal work environment.
So I'm kind of curious if anyone's ever run into a problem at their job that turned out to be NP-complete, and that the design needed to be changed to accommodate for it?
As the others have stated, the knapsack (for packing cargo) and traveling salesmen problem are probably the most common "real world" NP-complete problems.
I tend to run into problems at work that can't be proven to be NP complete or incomplete because they're not very well defined.