Fruit Share (Dynamic Programming)

Question

It is very difficult for me to try to figure out how to solve this problem effectively. Let me describe how this happens:

“A hardworking mother bought several fruits with different nutritional values ​​for her 3 children, Amelia, Jessica and Bruno. Both girls are overweight and they are very vicious and always leave poor Bruno with nothing, so their mother decided to share the food as follows:

• Amelia, the hardest, gets the most nutritional value
• Jessica receives an amount equal to or less than Amelia
• Bruno receives an amount equal to or less than Jessica, but you need to find a way to give him the highest possible nutritional value while following the rule (A> = J> = B) "

Note. The original problem is described in different ways, but the idea is the same, I do not want my classmates to find this post when they google helped hehe.

One of the test cases given by my teacher is as follows:

The fruit list has the following values { 4, 2, 1, 8, 11, 5, 1} Input: 7 -----> Number of Fruits 4 2 1 8 11 5 1 ----> Fruits Nutritional Values Output: 1 11 ----> One fruit, their nutritional values sum for Amelia 5 ----> Position of the fruit in the list 3 11 ----> Three fruits, their nutritional values sum for Jessica 1 2 6 ----> Position of the fruits in the list 3 10 ----> Three fruits, their nutritional values sum for Bruno 3 4 7 ----> Position of the fruits in the list 

Note. I know that there are several ways of diving fruit among children, but it does not matter if it follows the rule A> = J> = B.

First, I made an algorithm that generated all the subsets, each of which had its own amounts and positions that were used. This method was quickly discarded because the list of fruits can contain up to 50 fruits, and the subset can be O (2 ^ n). I have run out of memory.

The second idea I have is to use dynamic programming. In the column heading I would have the positions of the fruit list, in the row heading the same thing, it is difficult to explain with letters, so I will do the table for the previous example {4, 2, 1, 8, 11, 5, 1}.

  00 01 02 03 04 05 06 07 00 01 02 03 04 05 06 07 

Each time we go to the line below, add the positions 1,2,3, ..., 7

  00 01 02 03 04 05 06 07 00 00 <---No positions in use 01 04 <---RowPosition 1 + Column Position(Column 0) (4+0) 02 06 <---RowPosition 1 + RowPosition 2 + Column Position (4+2+0) 03 07 <---RP(1) + RP(2) + RP(3) + CP(0) (4+2+1+0) 04 15 <--- (4+2+1+8+0) 05 26 06 31 07 32 <--- (4+2+1+8+11+5+1+0) 

Now that you know how to do this, add the first line

  00 01 02 03 04 05 06 07 00 00 04 02 01 08 11 05 01 <-- Sum of RP + CP 01 04 00 06 05 12 15 09 05 <-- Sum of RP(0..1) + CP 02 06 03 07 04 15 05 26 06 31 07 32 

I put 00 because the 1st position is already in use. The completed table will look as follows.

  00 01 02 03 04 05 06 07 00 00 04 02 01 08 11 05 01 01 04 00 06 05 12 15 09 05 02 06 00 00 07 14 17 11 07 03 07 00 00 00 15 18 12 08 04 15 00 00 00 00 26 20 16 05 26 00 00 00 00 00 31 27 06 31 00 00 00 00 00 00 32 07 32 00 00 00 00 00 00 00 

Now that we have a table. I divide the Nutrient value by the number of children, 32/3 = 10.6667, the ceiling will be 11. I try to check 11, if it is in the table, I select it and mark the position of the rows and columns of the tables used, then I would try to check 11 again. if in the table I select it differently by looking at 10 or 9, etc., until I find it. Subsequently, I would identify the relevant positions that were used, and then summarize the unused positions to get Bruno’s benefits.

I know that there should be a better way to do this, because I found a flaw in my method, the table has only the sum of several subsets. Therefore, perhaps this will be detrimental in several test cases. Maybe a 3D Memoization Cube ?, I think it will consume too much memory, and I have a limit of too 256 MB.

Wow, I didn’t understand that I got so many xX. I hope I don’t get a lot of TL; DR. Any help / guidance would be greatly appreciated: D

EDIT: I created code that generates a table if someone wants to try it.

 static void TableGen(int[] Fruits) { int n = Fruits.Length + 1; int[,] memo = new int[n, n]; for (int i = 1; i < n; i++) { memo[0, i] = Fruits[i - 1]; memo[i, 0] = memo[i - 1, 0] + Fruits[i - 1]; for (int j = i + 1; j < n; j++) memo[i, j] = memo[i, 0] + Fruits[j - 1]; } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) Console.Write("{0:00} ", memo[i, j]); Console.WriteLine(); } } 

Answer 1

  for(i = 0; i < count; i++) { currentFruit=Fruits.Max(); if(Amelia.Sum() + currentFruit < Jessica.Sum() + currentFruit) { Amelia.Add(currentFruit); Fruits.Remove(currentFruit); continue; } if(Jessica.Sum() + currentFruit < Bruno.Sum() + currentFruit) { Jessica.Add(currentFruit); Fruits.Remove(currentFruit); continue; } Bruno.Add(currentFruit); Fruits.Remove(currentFruit); } 

This works for fruits with relatively close values. If you add a fruit whose value is greater than all the other fruits combined (which I did once by chance), it breaks a little.

Answer 2

A slightly computationally intensive method would be to prescribe the fruit in a circular manner, starting with the highest nutritional value for amelia.
From there, gradually sort out the fruit with the lowest nutritional value that amelia holds, and try each combination: (a) giving the fruit to jessica or (b) replacing the fruit with one held by jessica, while still satisfying the rule. Then apply the same method to jessica and bruno. Repeat these 2 cycles until more swaps or dates appear.
A little more complicated, but potentially faster, would be to simultaneously give / exchange for jess / bruno. For every 2 slices of fruit that A holds, you will have 4 options to try, with plenty if you try to balance J and B at the same time.

For a faster algorithm, you can try asking the math stack exchange site, since this is a very problem in set theory.