« 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


Take a tour of the entire planet of Neopia.
Learn the meaning to all Neopian words, phrases and acronyms!
Help us model your pets!
All the hottest looks, try them on today!
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

Below we consider a few items, the goal of maximise total joodles in the bag, and a bag with capacity 6.

Item NameQuantityWeightValue
Anchorberry3550
Snow Cabbage1330
Starberry2225

The first step is to remove duplicates by making extra rows and adding item numbers:

Item NameItem NumberWeightValue
Anchorberry1550
Anchorberry2550
Anchorberry3550
Snow Cabbage4330
Starberry5225
Starberry6225

Next we build the empty chart of size (C+1)x(N+1). In this case N (the number of items) is 6 and C (the capacity) is 6. Maximum item number will be in green and maximum capacity in purple to avoid confusion.

0123456
6
5
4
3
2
1
0

The next step is to fill in a maximum value of 0 for the entire 0 item column, and 0 capacity row.

0123456
60
50
40
30
20
10
00000000

Now, we patiently start filling all 36 remaining cells. For capacity 1, max item number 1 we cannot add item 1 (which is the only item considered), so we must use capacity 1, max item number 0 (1-1). The value in that cell was 0, so we copy that to this cell.

0123456
60
50
40
30
20
100
00000000

For capacity 1, max item number 2 we cannot add item 1 or 2, so we must use capacity 1, max item number 1 (2-1). The value in that cell was 0, so we copy that to this cell. In fact, since no items are of weight 1 or smaller, we can just fill in 0 for all the capacity 1 cells since the result will be the same, no matter the maximum item.

0123456
60
50
40
30
20
10000000
00000000

For capacity 2, max item number 1 we cannot add item 1, so we must use capacity 2, max item number 0 (1-1). The value in that cell was 0, so we copy that to this cell. Since items 1 through 4 are of weight 3 or bigger, we can just fill in 0 for max item numbers 1 through 4, capacity 2 cells. We could do this step by step, of course, and would get the same result.

0123456
60
50
40
30
200000
10000000
00000000

For capacity 2, max item number 5 we CAN add item 5. Then we consider:

  • Adding item 5: 25 (item 5's value) + 0 (the cell for capacity 0, max item number 4) = 25
  • Not adding item 5: 0 (the value from the cell for capacity 2, max item number 4)
The better choice is 25, so we put 25 in this cell.

0123456
60
50
40
30
20000025
10000000
00000000

For capacity 2, max item number 6 we CAN add item 6. Then we consider:

  • Adding item 6: 25 (item 6's value) + 0 (the cell for capacity 0, max item number 5) = 25
  • Not adding item 6: 25 (the value from the cell for capacity 2, max item number 5)
It's a tie, which means 25 is still the biggest number available (it's just also the smallest available). We put 25 in the cell for capacity 2, max item number 6. This makes sense - item 5 and item 6 are identical so it doesn't matter which of the two are used, the maximum value is the same.

0123456
60
50
40
30
2000002525
10000000
00000000

That's 12 of the aforementioned 36 cells out of the way, 24 to go. For capacity 3, max item number 1 through max item number 3, we can't fit any item in the bag. This means we can put a 0 in the cells for capacity 3, max item number 1, max item number 2, and max item number 3.

0123456
60
50
40
30000
2000002525
10000000
00000000

For capacity 3, max item number 4 we CAN add item 4. Then we consider:

  • Adding item 4: 30 (item 4's value) + 0 (the cell for capacity 0, max item number 3) = 30
  • Not adding item 4: 0 (the value from the cell for capacity 3, max item number 3)
30 is clearly the larger value, so we put 30 in the cell.

0123456
60
50
40
3000030
2000002525
10000000
00000000

For capacity 3, max item number 5 we CAN add item 5. Then we consider:

  • Adding item 5: 25 (item 5's value) + 0 (the cell for capacity 1, max item number 4) = 25
  • Not adding item 5: 30 (the value from the cell for capacity 3, max item number 4)
30 is clearly the larger value, so we put 30 in the cell. The same thing will happen for capacity 3, max item number 6, so we can put 30 in that cell as well.

0123456
60
50
40
30000303030
2000002525
10000000
00000000

That's 18 of the aforementioned 36 cells out of the way, 18 to go. For capacity 4, max item number 1 through max item number 3, we can't fit any item in the bag. This means we can put a 0 in the cells for capacity 4, max item number 1, max item number 2, and max item number 3.

0123456
60
50
40000
30000303030
2000002525
10000000
00000000

For capacity 4, max item number 4 we CAN add item 4. Then we consider:

  • Adding item 4: 30 (item 4's value) + 0 (the cell for capacity 1, max item number 3) = 30
  • Not adding item 4: 0 (the value from the cell for capacity 4, max item number 3)
30 is clearly the larger value, so we put 30 in the cell.

0123456
60
50
4000030
30000303030
2000002525
10000000
00000000

For capacity 4, max item number 5 we CAN add item 5. Then we consider:

  • Adding item 5: 25 (item 5's value) + 0 (the cell for capacity 2, max item number 4) = 25
  • Not adding item 5: 30 (the value from the cell for capacity 4, max item number 4)
30 is clearly the larger value, so we put 30 in the cell.

0123456
60
50
400003030
30000303030
2000002525
10000000
00000000

For capacity 4, max item number 6 we CAN add item 6. Then we consider:

  • Adding item 6: 25 (item 6's value) + 25 (the cell for capacity 2, max item number 5) = 50
  • Not adding item 6: 30 (the value from the cell for capacity 4, max item number 5)
50 is clearly the larger value, so we put 50 in the cell. This cell right now says that given all the items, if the capacity of the bag was 4, the best choice would be to pick items 5 and 6 for a maximum value of 50. Of course our bag has more capacity so we have to keep going just in case a better maximum value comes up.

0123456
60
50
40000303050
30000303030
2000002525
10000000
00000000

For capacity 5, max item number 1 we CAN add item 1. Then we consider:

  • Adding item 1: 50 (item 1's value) + 0 (the cell for capacity 0, max item number 0) = 50
  • Not adding item 1: 0 (the value from the cell for capacity 5, max item number 0)
50 is clearly the larger value, so we put 50 in the cell.

0123456
60
5050
40000303050
30000303030
2000002525
10000000
00000000

For capacity 5, max item number 2 we CAN add item 2. Then we consider:

  • Adding item 2: 50 (item 2's value) + 0 (the cell for capacity 0, max item number 1) = 50
  • Not adding item 2: 50 (the value from the cell for capacity 5, max item number 1)
50 is clearly the largest value either way, so we put 50 in the cell.

0123456
60
505050
40000303050
30000303030
2000002525
10000000
00000000

For capacity 5, max item number 3 we CAN add item 3. Then we consider:

  • Adding item 3: 50 (item 3's value) + 0 (the cell for capacity 0, max item number 2) = 50
  • Not adding item 3: 50 (the value from the cell for capacity 5, max item number 2)
50 is clearly the largest value either way, so we put 50 in the cell.

0123456
60
50505050
40000303050
30000303030
2000002525
10000000
00000000

For capacity 5, max item number 4 we CAN add item 4. Then we consider:

  • Adding item 4: 30 (item 4's value) + 0 (the cell for capacity 2, max item number 3) = 30
  • Not adding item 4: 50 (the value from the cell for capacity 5, max item number 3)
50 is clearly the larger value, so we put 50 in the cell.

0123456
60
5050505050
40000303050
30000303030
2000002525
10000000
00000000

For capacity 5, max item number 5 we CAN add item 5. Then we consider:

  • Adding item 5: 25 (item 5's value) + 30 (the cell for capacity 3, max item number 4) = 55
  • Not adding item 5: 50 (the value from the cell for capacity 5, max item number 4)
55 is clearly the larger value, so we put 55 in the cell.

0123456
60
505050505055
40000303050
30000303030
2000002525
10000000
00000000

For capacity 5, max item number 6 we CAN add item 6. Then we consider:

  • Adding item 6: 25 (item 6's value) + 30 (the cell for capacity 3, max item number 5) = 55
  • Not adding item 6: 55 (the value from the cell for capacity 5, max item number 5)
55 is clearly the largest value either way, so we put 55 in the cell.

0123456
60
50505050505555
40000303050
30000303030
2000002525
10000000
00000000

We're down to just 6 cells to go. For capacity 6, max item number 1 we CAN add item 1. Then we consider:

  • Adding item 1: 50 (item 1's value) + 0 (the cell for capacity 3, max item number 0) = 50
  • Not adding item 1: 0 (the value from the cell for capacity 6, max item number 0)
50 is clearly the larger value, so we put 50 in the cell.

0123456
6050
50505050505555
40000303050
30000303030
2000002525
10000000
00000000

For capacity 6, max item number 2 we CAN add item 2. Then we consider:

  • Adding item 2: 50 (item 2's value) + 0 (the cell for capacity 3, max item number 1) = 50
  • Not adding item 2: 50 (the value from the cell for capacity 6, max item number 1)
50 is clearly the largest value either way, so we put 50 in the cell. The same thing will happen for capacity 6, max item number 3 so we can put 50 in that cell while we're at it.

0123456
60505050
50505050505555
40000303050
30000303030
2000002525
10000000
00000000

For capacity 6, max item number 4 we CAN add item 4. Then we consider:

  • Adding item 4: 30 (item 4's value) + 0 (the cell for capacity 3, max item number 3) = 30
  • Not adding item 4: 50 (the value from the cell for capacity 6, max item number 3)
50 is clearly the larger value, so we put 50 in the cell.

0123456
6050505050
50505050505555
40000303050
30000303030
2000002525
10000000
00000000

For capacity 6, max item number 5 we CAN add item 5. Then we consider:

  • Adding item 5: 25 (item 5's value) + 30 (the cell for capacity 4, max item number 4) = 55
  • Not adding item 5: 50 (the value from the cell for capacity 6, max item number 4)
55 is clearly the larger value, so we put 55 in the cell.

0123456
605050505055
50505050505555
40000303050
30000303030
2000002525
10000000
00000000

We're on the last cell now! For capacity 6, max item number 6 we CAN add item 6. Then we consider:

  • Adding item 6: 25 (item 6's value) + 30 (the cell for capacity 4, max item number 5) = 55
  • Not adding item 6: 55 (the value from the cell for capacity 6, max item number 5)
55 is clearly the largest value either way, so we put 55 in the cell.

0123456
60505050505555
50505050505555
40000303050
30000303030
2000002525
10000000
00000000

After all that hard work, we now have a filled out chart. Looking at the capacity 6, max item number 6 we see that the maximum value in this case is 55. There aren't a whole lot of combinations here so you can convince yourself that this is the case just by looking at the items and trying picking different items. We are interested in backtracking to figure out what the actual items are though, so let's backtrack step by step.

  • Current Items: None, Current Position: max item number 6, capacity 6
    We could have chose to use item 6 or not use item 6. Since either way would have given us the same maximum value (55), we'll choose not to use item 6. We'll do this for every tie for consistency, but there's no reason you can't choose to include the item instead.
  • Current Items: None, Current Position: max item number 5, capacity 6
    The only way to get 55 in this cell was if we added item 5, and used the best result from max item number 4, capacity 4. This is because looking at the list of items we made at the beginning, we see item #5 (Starberry) weighs 2g. Since the current position considered a capacity of 6g, and 6g-2g=4g we must consider maximum capacity 4g. We already considered items #6 and #5, so the next available item is #4. So the new current position will be max item number 4, capacity 4.
  • Current Items: #5, Current Position: max item number 4, capacity 4
    The only way to get 30 in this cell was if we added item 4, and used the best result from max item number 3, capacity 1.
  • Current Items: #4, #5, Current Position: max item number 3, capacity 1
    This cell has a maximum value of 0, so we're done!
Items #4 and #5 correspond to Snow Cabbage and one of the Starberries in our numbered chart from the top of the page, so that's our final answer.

This approach seems like a whole lot of work for not very much benefit - you probably could have figured out what the best set of items was in this example way faster by just looking at the items for a minute. However, this approach has the advantage of following the same process no matter how big the capacity or number of items. Just imagine if the maximum capacity was 3,000 and there were 500 different items. That's 1,500,000 cells (or 1,503,501 cells if you include the 0 capacity / 0 item cells) but that's way better than trying to add up values for all the different combinations of items (of which there will be "2 to the power of 500" - a number that's larger than 1 with 150 zeros after it!).