In the tradition of my Holiday MathPuzzles, I’m here with an appropriately themed puzzle for this time of year.

Candy Distribution

It’s that time of year all right. You’re out and about, trick or treating with your friends or family and when you come home, you decide to dump all the candy out on the floor to sort through it. But then, as siblings often do, you begin to bicker about who has “more” than the other. In fact, there are some candies that you really like, and some you don’t like. You’d rather have a bunch of chocolate than a bunch of peppermints, for instance. But wait a minute! Of course you can’t like the same thing! Your sibling actually likes peppermints!

Here’s a table of the different candies you have. Each candy has a “value” to it; that is, how much you “want” it. Try to split up the candies such that you and your sibling both have as equal value as possible at the end. And no fighting!

This post continues my series on intractable problems. In this installment, I will talk about problems relating to Data Storage. As a refresher, remember that an intractable problem is one that is very computationally complex and very difficult to solve using a computer without some sort of novel thinking. I will discuss two famous problems related to Data Storage below, as well as provide a few examples and references.

Part Two — Data Storage

Knapsack — given a set of items with weights and values , and a knapsack with capacity , maximize the value of the items in the knapsack without going over capacity.

To start with, here is a small example that I refer to in this previous post. If you’re trying to place ornaments on a tree, you want to get the max amount of coverage possible. However, the tree can only hold so much weight before it falls over. What is the best way to pick ornaments and decorations such that you can cover as much of the tree as possible without it falling over?

I actually saw a really interesting video describing an example of this problem in this video (watch the first few minutes). The professor here sets up a situation of Indiana Jones trying to grab treasures from a temple before it collapses. He wants to get the most valuable treasures he can, but he can only carry so much.

Class: There are several different types of knapsack problems, but the most common one (the one discussed above) is one-dimensional knapsack. The decision problem (can we get to a value without exceeding weight ?) is NP-Complete. However, the optimization problem (what is the most value we can get for the least weight?) is NP-Hard.

References:

Wikipedia Page – General discussion of the Knapsack problem, different types, complexity, and a high level view of several algorithms for solving

Bin Packing— given a set of items with weights and a set of bins with capacity each, place the items into the bins such that the minimum amount of bins are used.

This problem is very similar to the knapsack problem found above, but this time we don’t care how much the items are worth. We just want to pack them in the smallest area possible. Solving this problem is invaluable for things like shipping and logistics. Obviously, companies want to be able to ship more with less space.

A more commonplace example could be thinking of this problem as Tetris in real life. Consider that you’re moving to a new place, and you have you and your friends car in which to move things. How can you place all the items in your cars such that you take up space the most efficiently?

Some progress has been made on reasonably large data sets by using what is called the “first fit decreasing algorithm”. This means that you pick up an item, and place it into the first bin that it will fit in. If it can’t fit in any of the current bins, make a new bin for it. Decreasing means that before you start placing items, you sort them all from biggest to smallest. You probably do this in your everyday life. If you want to pack a box, you start with the big items, right? No need to put lots of small items on the bottom. By getting the big items out of the way first, you can be more flexible with the remaining space because you will then have smaller items.

Class: This problem is NP-Hard.

References:

Wikipedia Page – a high level description of the problem

First Fit Decreasing Paper (pdf) – this is a technical paper describing computational bounds for using the first fit decreasing algorithm. Not for beginners.

Merry Christmas and Happy Holidays to everyone, I’m back with a new holiday themed puzzle to distract your mind away from annoying family members or holiday stress.

#2: Santa needs to deliver his presents, and fast! He has a map of the towns he needs to go to, but he doesn’t have much time left before Christmas is over! Help him deliver some last minute gifts in the shortest distance possible. You must visit every town at least once (duplicates are allowed, but for bonus points see if you can visit each town only once and still be as quick as possible). Each node in the graph is a town and the weight of each edge represents how far it is from one town to another. (Note: graph is not to scale)

That time of year is upon us once again, and what better way to celebrate than by doing a few holiday-themed puzzles?

#1: You brought home the perfect tree to decorate; however, it can only hold 10kg of decorations before the branches start to sag and it falls over. In addition, you can’t have too many items on the tree, there’s only so much space. Because of this, you only can hang 25 decorations of any kind at one time. These are the decorations you have available:

Type of Decoration

Weight (each)

Coverage (% of tree covered, each)

Tinsel (limit 1)

1kg

7%

Plastic Ornaments

0.1kg

1%

Glass Ornaments

0.4kg

5%

Angel Topper (limit 1)

2kg

10%

Popcorn String (limit 1)

0.75kg

6%

Icicle Hangers

0.25kg

3%

Lights (limit 1)

2.5kg

20%

We want to get the most covered tree we can without going over the weight limit. What is the lightest and most covered tree combination you can find?