Snowager alert!
« January »
January
Jan 3 - Aisha Day
Jan 6 - Gnorbu Day
Jan 11 - Buzz Day
Jan 14 - Sloth Day
Jan 16 - Elephante Day
Jan 29 - Kacheek Day


A searchable database of Neopets images
Earn NP from playing games!
Join a large Neopets community!
Discover the characters of Neopia in our Book of Ages!
Your jnAccount! Your jnAccount: Login or Register | New to Jellyneo? Click here!

Negg Hunt '11 Scheduling and Supply Solutions

Negg Hunt '11 Logo
High-Scores | Solutions | Portals | Memorable Comments

Scheduling Content Puzzle | Supplies in a Bag Puzzle

Contents:

  1. Supply Room Solutions
  2. How to Solve Supply Room Puzzles
  3. Solving Supply Room Puzzles Example
  4. Kaurevir's Puzzle Solution

It goes without saying that solving this problem is harder than solving the scheduling problem. That doesn't mean it's unsolvable though. Before telling you a proper solution, we're going to show the "ratio" solution, and point out why it doesn't necessarily work. Don't worry if you don't know what a ratio is, it's about to be explained. First, though to explain "value".

Value sounds pretty obvious - you would think it's just how many joodles the item is worth. In fact though, "value" refers to how much benefit we get out of picking an item. So for Kaurevir and Torratz, value is the joodle amount. In the case of Dream though, value is the weight of the item. This is because for Dream, any item only gives the benefit of its weight - if two items are both 300g and one is worth 500 joodles while the other is worth 50000 joodles, no matter which one we pick we still only have gained 300g. For Zelda, the value of each item is even simpler. Since Zelda just wants the most items, each item contributes the same amount towards her goal no matter the weight or cost. So each item can have a value of 1 since they're all equal. If you for some reason wanted to set the value to something else, as long as all items had the same value, you would be accurately representing "value". To summarise:

  • If you want the most items, set the value of each item to 1.
  • If you want the most weight, set the value of each item to its weight.
  • If you want the most joodles, set the value of each item to its price in joodles.

A ratio of A to B (sometimes written as A:B or A/B) says how many As there are to every B or what the "A per B" is. In our case, this could be useful, since we could figure out how much value there is per weight unit (g). Since weight is what limits how much we can take, we want the most value for every unit of weight we get. Well, actually that isn't true, but it's a good idea. We'll be showing why that isn't the case shortly. Let's come up with a way to use ratios to solve the supply room problem. If we had a chart that showed the ratios, and sorted by the highest ratio first, we could just take as much of that one as possible, move on to the next best ratio and take as much of that item as possible, and so on until we either took everything or our bag was full. In other words:

  1. Make a chart with all the items, quantities, weights, and spaces for both value and ratio.
  2. Fill in the value for each item using the rules from the previous paragraph.
  3. Fill in the ratio for each item: ratio = value / weight
  4. Keep taking one of the best ratio item that will still fit in the bag, until nothing else fits in the bag.
We claim this solution isn't actually right. Let's see what happens when we do it to Kaurevir's puzzle.

Item NameQuantityWeightValueRatio
Dung Folder44171017.31
Vanishing Ink32746017.04
Berry Ink Pen693137014.73
Doglefox Jelly1380541014.24
Sloth Ruler26488013.75
Spacerocked Stapler5119161013.53
Notebook of Surprising Secrets46274011.94

Since we've made the chart ordered by ratio, we can now see what the solution would be using the "highest ratio first" approach. Kaurevir's bag at each step is detailed below:

  • Empty (0/491g)
  • Dung Folder x1 (41/491g)
  • Dung Folder x2 (82/491g)
  • Dung Folder x3 (123/491g)
  • Dung Folder x4 (164/491g)
  • Dung Folder x4, Vanishing Ink x1 (191/491g)
  • Dung Folder x4, Vanishing Ink x2 (218/491g)
  • Dung Folder x4, Vanishing Ink x3 (245/491g)
  • Dung Folder x4, Vanishing Ink x3, Berry Ink Pen x1 (338/491g)
  • Dung Folder x4, Vanishing Ink x3, Berry Ink Pen x2 (431/491g)
After this, there's not enough room for the lightest item left (62g), so we're done. Let's add up the values now: 4*710 + 3*460 + 1*1370 = 5590 joodles. But the actual solution got Kaurevir 7620 joodles, which is bigger than what we just found. So this method doesn't actually work. :( In fact, none of the following will work:
  • Picking the highest or lowest ratio items first
  • Picking the heaviest or lightest items first
  • Picking the highest or lowest value items first

So why didn't "highest ratio first" work? The problem is that it may be possible to pack in more items if we pick some items to be lighter, even if they have a worse ratio. If there is a choice between putting in both a very heavy very expensive gold brick and nearly worthless but very light pebble, or putting in several lighter silver bricks that are worth more than pebbles but less than gold, the silver bricks may be a better option. If you're familiar with averages, you can also think of this as the "highest ratio first" doesn't guarantee the best average ratio.

None of the approaches mentioned above worked - so is this hopeless? Did the Negg Hunt use some dark magic to check our answers? Did Rosie and Kataklysmos sit down and try every combination of items to figure out what the best solution was? Of course not! To solve this problem, we start again with some simple observations:

  • Every item is either in a best solution, or it isn't.
  • A bag with capacity of 0g has a maximum value of 0.
  • Any bag, no matter what its capacity is, will have a maximum value of 0 if there are no items that can be added (so when there are 0 items and when there are just no items that will fit).
  • If for a bag of capacity C we use one item I with weight W, the best solution will be the value of I plus the best value of a bag with capacity C-W considering all remaining items.
From this we can create a solution, but it takes a lot of space - we have to consider every item similar to how we did every article in the scheduling problem, and every possible bag capacity from 1 to whatever the actual bag capacity is. Worse yet, when we have duplicate items, we have to treat each item as a separate item. For this reason it's best to first make an extended chart where if an item had a quantity of Q where Q was larger than 1, it now has Q rows where the quantity is 1 in each row. After doing this, it's best to number all the items so you have a unique way of referring to them. Now then, if we have a total of N rows in our extended chart, and the bag capacity is C, we will have to make a chart of size CxN. That gets pretty big pretty fast, so this isn't a good approach for scratch paper. It is however, an excellent use for spreadsheet software like Excel, Quattro Pro, or OpenOffice CALC.

Regardless of how we're going to keep track of our chart, we have to fill it in still. Each spot represents the maximum value for a particular capacity bag considering only a certain number of items (starting with item 1). To make things easier, you should actually make a (C+1)x(N+1) chart so that you can have a 0 weight row or column, and a 0 item row or column. We can fill in both of the 0 cases with 0, so that gets rid of a lot of work. For any cell that isn't for 0 items or 0 capacity (say it's for items 1 through I and capacity D), we can fill it in by picking the larger of two values (or one value if item I can't fit):

  • The case where we add item I: I's value + the cell for item I-1 with capacity D-(I's weight)
  • The case where we don't add item I: The cell for item I-1 with capacity D.
Why does this work? It works since we already figured out the best solution for a smaller set of items both with the same capacity, and smaller capacities, we already know what the best solutions will be for the first I-1 items, and whether or not we include item I is a choice with only two options. Wait a second though - we never said what the order for filling in this table is. The previous observation points out that order DOES matter. Since we're considering more and more items, it makes sense that we should fill out everything for item 1 before items 1 through 2, which we should fill out before items 1 through 3, and so on. We also have to fill in the cells for smaller capacities first. So in short, the procedure is:
  1. Make an extended chart if necessary to separate duplicate items, and number items in general.
  2. Update values to match whatever the goal is.
  3. Make a (C+1)x(N+1) chart.
  4. Fill in all the cells with a 0 capacity or 0 items with 0.
  5. Starting with the column or row for only considering item 1, fill in capacity 1, then capacity 2 and so on, all the way up to capacity C.
  6. Repeat the previous step for the column or row considering items 1 and 2, then 1 through 3, and so on up to items 1 through N.
  7. The maximum value is in the cell for capacity C considering all N items.

Finding what the maximum value is can be useful, but we wanted to know WHICH items give us the maximum value. To find out, we'll do a bit of backtracking. Starting at the cell for capacity C and all N items, we figure out which of the two choices gave it the maximum value that we put in that cell. If both choices give the same maximum value, that means there's a tie and we can choose either option. Go to the cell that gave the maximum value, and figure out how it got its maximum value. Repeat this until you get to a cell where the maximum value is 0. While backtracking, every time you took the choice of "Add item I", that means I is in the solution. A small example can be found here, but due to the size of these charts it's for a smaller example. If you're interested in seeing what Kaurevir's table looks like using this method but not a step by step guide, you can see it here.