Skip to main content
Home
plus.maths.org

Secondary menu

  • My list
  • About Plus
  • Sponsors
  • Subscribe
  • Contact Us
  • Log in
  • Main navigation

  • Home
  • Articles
  • Collections
  • Podcasts
  • Maths in a minute
  • Puzzles
  • Videos
  • Topics and tags
  • For

    • cat icon
      Curiosity
    • newspaper icon
      Media
    • graduation icon
      Education
    • briefcase icon
      Policy

      Popular topics and tags

      Shapes

      • Geometry
      • Vectors and matrices
      • Topology
      • Networks and graph theory
      • Fractals

      Numbers

      • Number theory
      • Arithmetic
      • Prime numbers
      • Fermat's last theorem
      • Cryptography

      Computing and information

      • Quantum computing
      • Complexity
      • Information theory
      • Artificial intelligence and machine learning
      • Algorithm

      Data and probability

      • Statistics
      • Probability and uncertainty
      • Randomness

      Abstract structures

      • Symmetry
      • Algebra and group theory
      • Vectors and matrices

      Physics

      • Fluid dynamics
      • Quantum physics
      • General relativity, gravity and black holes
      • Entropy and thermodynamics
      • String theory and quantum gravity

      Arts, humanities and sport

      • History and philosophy of mathematics
      • Art and Music
      • Language
      • Sport

      Logic, proof and strategy

      • Logic
      • Proof
      • Game theory

      Calculus and analysis

      • Differential equations
      • Calculus

      Towards applications

      • Mathematical modelling
      • Dynamical systems and Chaos

      Applications

      • Medicine and health
      • Epidemiology
      • Biology
      • Economics and finance
      • Engineering and architecture
      • Weather forecasting
      • Climate change

      Understanding of mathematics

      • Public understanding of mathematics
      • Education

      Get your maths quickly

      • Maths in a minute

      Main menu

    • Home
    • Articles
    • Collections
    • Podcasts
    • Maths in a minute
    • Puzzles
    • Videos
    • Topics and tags
    • Audiences

      • cat icon
        Curiosity
      • newspaper icon
        Media
      • graduation icon
        Education
      • briefcase icon
        Policy

      Secondary menu

    • My list
    • About Plus
    • Sponsors
    • Subscribe
    • Contact Us
    • Log in
    • Plus Advent Calendar Door #24: Santa's knapsack problem

      24 December, 2013
      Will the presents fit?

      Santa's just putting his hat on and button up his jolly red coat when an exasperated elf runs up to him: "Santa! We've got a problem! There have been so many good children this year we can't put all the presents into your sleigh!"

      The problem is that Santa's sleigh has a weight limit, and can only carry 2 tonnes of present. Each present has a different weight, and each present has a different star value too: a star for each good deed of the toy's recipient. Santa obviously wants to reward as many good deeds as possible, maximising the total star value of the presents in the sleigh. But he can't exceed the maximal weight or those presents are going nowhere! So which should he put in his sleigh?

      The elves start out trying all different combinations of presents to find the best one. This would have been fine if there only were a few items, but they quickly realise it is totally impractical when you have millions of presents to deal with. If they carry on this way Christmas Eve will have long passed and no presents at all will be delivered!

      Such a brute force solution is unacceptable, and not only to the elves and Santa. Mathematicians would also find this an unacceptable approach, and ask whether there is an algorithm – a recipe for finding a solution – which works for any number of items, and so that the time it takes to complete the algorithm grows with the number of items in a reasonable, non-explosive fashion.

      Mathematicians have a clear definition of "reasonable and non- explosive" in this context: the time it takes to complete the algorithm should grow with the number N of items no faster than the polynomial N to the power of K, for some integer K, grows with N. That's still pretty rapid growth, especially if K is large, but at least it's not exponential.

      So does such a polynomial time algorithm exist for our problem? The answer is that nobody knows - not yet - though most mathematicians believe that there isn't. In fact, if you can prove or disprove that a polynomial time algorithm exists you will have answered the question behind door #22 too, as they both can be turned into NP complete problems.

      Optimisation problems such as this one, which is known as the knapsack problem, crop up in real life all the time. Thankfully Santa is well read in mathematical literature and knows an algorithm they can use that won't take too long and, while it not give the very best combination of starred pressies, it will get sufficiently close.

      So rest assured, if you've been really, really good, your present is probably now packed on the sleigh, ready for the Santa's big delivery run. Merry Christmas!

      You can find out more about NP complete problems on Plus.

      Back to the Plus Advent Calendar

      Read more about...
      Advent calendar 2013
      • Log in or register to post comments

      Read more about...

      Advent calendar 2013
      University of Cambridge logo

      Plus Magazine is part of the family of activities in the Millennium Mathematics Project.
      Copyright © 1997 - 2025. University of Cambridge. All rights reserved.

      Terms