December 7, 2014, by Graham Kendall

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

This post first appeared at Graham-Kendall.com.

For previous posts about Christmas, see here.

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.

Your task is to buy as many presents as possible which maximizes the number of points, whilst staying within your budget.

How difficult do you think it is to find a solution to this problem so that you daughter gets the best possible gifts such that there is not another selection of gifts that has a higher overall points value?

In fact, it is surprisingly difficult, especially as the number of available presents (and people you are buying for)  increases.

The problem is the so called Knapsack Problem, so named as you have knapsack which can carry a certain weight (your budget). Each item has a weight (cost of each item) but also a value (the number of points). You have to fill the knapsack, maximizing the value, but keeping the sum of all the weights less than the capacity of your knapsack.

Or, in terms of the Christmas Present Problem, you need to buy the best selection of presents to give the maximum number of points, while staying within your overall budget.

The Knapsack Problem is known to be an NP-Hard problem. These type of problems do not, as yet, have any efficient algorithm that can produce the optimal solution in reasonable time. At least for large sized problem instances. Hopefully, you can still give your daughter the best set of presents!

In fact, if you can find an efficient algorithm you could win one million dollars.

• Share on Facebook
• Share on Twitter
• Share on Google+
• Share on LinkedIn