# The Christmas Present Problem: It’s Hard – NP-Hard

As Christmas approaches, many of us are faced with the annual problem of who to buy presents for, how much to spend, what presents to buy and how to be fair to everybody.

Is this a tough problem to solve? Perhaps some science will help?

Let’s try and state the problem a little more precisely, and make it simple by assuming that we are buying presents for just one person. That does not detract from the more complex problem, especially if we establish that buying presents for one person is hard.

• You have to buy presents for just one person; your daughter
• You have a certain budget; an amount of money that you cannot excced
• You have a list of gifts that your daughter would like (we are assuming that she has been good so Father Christmas is willing to leave these gifts)
• To make life easier, you have given your daughter 100 points, and told her to assign a certain number of points to each item. The more points she assigns, the more likely she is to get that gift. For example, if she assigns all 100 points to just one gift (and zero points to the other gifts), then she is likely to get that gift. But if she assigns equal points to all gifts, then she is equally likely to get each item, but not all of them, as the total costs of the gifts bought cannot be more tha the overall budget.