Negg Hunt '11 Scheduling and Supply Solutions
High-Scores | Solutions | Portals | Memorable Comments
Scheduling Content Puzzle | Supplies in a Bag Puzzle
- Supply Room Solutions
- How to Solve Supply Room Puzzles
- Solving Supply Room Puzzles Example
- 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:
- Make a chart with all the items, quantities, weights, and spaces for both value and ratio.
- Fill in the value for each item using the rules from the previous paragraph.
- Fill in the ratio for each item: ratio = value / weight
- Keep taking one of the best ratio item that will still fit in the bag, until nothing else fits in the bag.
|Berry Ink Pen||6||93||1370||14.73|
|Notebook of Surprising Secrets||4||62||740||11.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)
- 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.
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.
- Make an extended chart if necessary to separate duplicate items, and number items in general.
- Update values to match whatever the goal is.
- Make a (C+1)x(N+1) chart.
- Fill in all the cells with a 0 capacity or 0 items with 0.
- 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.
- 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.
- 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.