Share Fruits Fairly (Programación dinámica)

Question

Me está costando mucho tiempo tratar de encontrar la forma de resolver este problema de manera eficiente. Déjame describir cómo va:

"Una madre trabajadora compró varias frutas con diferentes valores nutricionales para sus 3 hijos, Amelia, Jessica y Bruno. Ambas chicas tienen sobrepeso, y son muy viciosas y siempre dejan al pobre Bruno con nada, por lo que su madre decidió compartir la comida de la manera siguiente:

• Amelia siendo la más pesada recibe la mayor cantidad de valor nutricional
• Jessica recibe una cantidad igual o inferior a Amelia
• Bruno consigue una cantidad igual o inferior a Jessica, pero debe encontrar la manera de darle el valor nutricional más alto respetando la regla (A> = J> = B) "

Nota: El problema original se describe de manera diferente pero la idea es la misma, no quiero que mis compañeros encuentren esta publicación cuando buscan ayuda por Google, jeje.

Uno de los casos de prueba dadas por mi maestro es el siguiente:

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 

Nota: Soy consciente de que hay varias maneras de buceo de las frutas entre los niños, pero no tiene demasiada importancia ya siempre que siga la regla A> = J> = B.

Al principio hice un algoritmo que generaba todos los subconjuntos, cada uno tenía sus sumas y las posiciones que estaban en uso. Ese método se descartó rápidamente porque la lista de frutas puede tener hasta 50 frutos, y el algoritmo del subconjunto es O (2^n). Me quedé sin memoria.

La segunda idea que tengo es utilizar la Programación Dinámica. En el encabezado de las columnas tendría las posiciones de la lista de frutas, en el encabezado de la fila el mismo, es algo difícil de explicar con letras, por lo tanto, voy delante y hago la tabla para el ejemplo anterior {4, 2, 1, 8 , 11, 5, 1}.

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

Cada vez que avanzamos hacia la fila de abajo añadimos las posiciones 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) 

Ahora que ya sabe cómo va vamos a añadir la primera fila

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      

Pongo el 00 porque la 1ra posición ya está en uso. La mesa completa se vería así.

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  

Ahora que tenemos la tabla. Dividí la suma de los Valores nutricionales por la cantidad de hijos, 32/3 = 10.6667, el límite máximo sería 11. Intento verificar 11, si está en la tabla, lo elijo y marque la posición de la fila y columnas de las tablas como se usa, entonces trataría de verificar 11 nuevamente, si está en la tabla lo elijo, de lo contrario, mire el 10, o 9, etc. hasta que lo encuentre. Después marcaría las posiciones respectivas tal como se usa y luego sumaría las posiciones no utilizadas para obtener las frutas de Bruno.

Sé que tiene que haber una mejor manera de hacerlo porque encontré un error en mi método, la tabla solo tiene la suma de algunos subconjuntos. Entonces tal vez eso sea perjudicial en algunos casos de prueba. ¿Tal vez un Cubo de Memoización 3D ?, creo que consumiría demasiada memoria, y también tengo un límite de 256MB.

Wow, no me di cuenta escribí tanto x.X. Espero no obtener mucho Tl; Dr. Cualquier ayuda/guía sería muy apreciada: D

EDITAR: Hice el código que genera la tabla en caso de que alguien quiera probarlo.

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); 
    } 

Esto funciona para las frutas con valores relativamente similares. Si agrega una fruta cuyo valor es mayor que todas las otras frutas combinadas (lo que hice una vez por accidente) se descompone un poco.

Answer 2

Una manera levemente computacionalmente intensiva sería asignar la fruta de forma circular, comenzando con el valor nutricional más alto para amelia.
A partir de ahí, recorra progresivamente la fruta desde el valor nutricional más bajo contenido en amelia, y pruebe cada combinación de (a) dar la fruta a jessica, o (b) cambiar la fruta por una jessica, mientras satisface la regla. Luego aplique el mismo método a jessica y bruno. Repita estos 2 bucles hasta que no sean posibles más intercambios o dadas.
Un poco más complicado, pero potencialmente más rápido, sería dar/intercambiar simultáneamente a jess/bruno. Por cada 2 piezas de fruta que A tenga, usted tendrá 4 opciones para probar, con más si al mismo tiempo intenta equilibrar J & B.

Para un algoritmo más rápido, podría intentar preguntar en la pila de matemática sitio de intercambio, ya que este es en gran medida un problema de teoría de conjuntos.