That's a Wrap
Given a set of rectangular box dimensions, what is the smallest amount of paper that will wrap the box?
One would assume we want to cut out a rectangle of wrapping paper, since otherwise we get annoying scraps (and also the problem is mathematically trivial if we can cut a cross-type shape).
I haven't had any time to toy with this problem, but I had a feeling one particular MIT dude might have... and I was right. True to form, Erik Demaine delivers a whole page about various wrapping problems he's explored with colleagues.
To anyone reading who teaches a programming course, I would suggest that a fun algorithms assignment could be spun out problems of the above type. If the program outputted folding instructions too, so much the better.
Happy holidays, all!