Udostępniaj owoce w sposób rzetelny (programowanie dynamiczne)

Question

Bardzo trudno jest mi wymyślić, jak skutecznie rozwiązać ten problem. Pozwól mi opisać, jak to działa:

"Ciężko pracująca mama kupiła kilka owoców o różnych wartościach odżywczych dla swoich 3 dzieci, Amelii, Jessiki i Bruno. Obie dziewczyny mają nadwagę, są bardzo okrutne i zawsze zostawiają biednego Bruno z nic, więc ich matka postanowiła podzielić żywności w następujący sposób:

• Amelia jest najcięższym dostaje największą ilość Wartość odżywcza
• Jessica pobiera kwotę równą lub mniejszą niż Amelia
• Bruno dostaje kwota równa lub niższa niż Jessica, ale musisz znaleźć sposób, aby dać mu najwyższą możliwą wartość odżywczą przy zachowaniu zasady (A> = J> = B) "

Uwaga: pierwotny problem został opisany inaczej, ale pomysł jest taki sam, nie chcę, aby moi koledzy z klasy znaleźli ten wpis kiedy google o pomoc hehe.

Jednym z przypadków testowych podanych przez mojego nauczyciela jest następujący:

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 

Uwaga: Jestem świadomy, że istnieje kilka sposobów nurkowania owoców wśród dzieci, ale to naprawdę nie ma znaczenia, jak długo, jak wynika z zasady A> = J> = B.

Najpierw zrobiłem algorytm, który wygenerował wszystkie podzbiory, każdy miał swoje sumy i pozycje, które były w użyciu. Metoda ta została szybko odrzucona, ponieważ lista owoców może zawierać do 50 owoców, a algorytm podzbioru to O (2^n). Zabrakło mi pamięci.

Drugi pomysł, jaki mam, to użycie programowania dynamicznego. W nagłówku kolumny będę miał pozycje z Listy Owoców, w nagłówku tego samego nagłówka, to trochę trudno wytłumaczyć literami, więc naprzód zrobię tabelę dla poprzedniego przykładu {4, 2, 1, 8 11, 5, 1}.

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

każdym razem przejść do wiersza poniżej dodamy pozycji 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) 

teraz, że wiesz jak to idzie pozwala dodać pierwszy wiersz

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      

Ustawiłem 00, ponieważ pierwsza pozycja jest już w użyciu. Wypełniony stół wyglądałby tak.

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  

Teraz, gdy mamy stół. Dzielę sumę wartości odżywczych przez ilość dzieci, 32/3 = 10,6667, pułap będzie wynosił 11. Próbuję sprawdzić na 11, jeśli jest w stole, wybieram i zaznaczam pozycję rzędu i kolumn używanych stołów, wtedy spróbowałbym ponownie sprawdzić 11, jeśli jest w tabeli, wybieram go inaczej wyglądają 10, lub 9 itd, dopóki go nie znajdę. Następnie zaznaczam odpowiednie pozycje, a następnie sumuję niewykorzystane pozycje, aby uzyskać owoce Bruna.

Wiem, że musi być lepszy sposób, aby to zrobić, ponieważ znalazłem błąd w mojej metodzie, tabela ma tylko sumę kilku podzbiorów. Może to będzie szkodliwe w kilku testowych przypadkach. Może 3D Memoization Cube ?, myślę, że zużyje za dużo pamięci, a ja mam limit zbyt 256 MB.

Wow, nie zdawałem sobie sprawy, że wpisałem tyle X.X. Mam nadzieję, że nie dostanę dużo tl; dr. Każda pomoc/przewodnik będzie bardzo mile widziana: D

EDYCJA: Zrobiłem kod, który generuje tabelę na wypadek, gdyby ktoś chciał ją wypróbować.

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

Działa to dla owoców o stosunkowo podobnej wartości. Jeśli dodasz owoc, którego wartość jest większa niż wszystkie inne owoce razem (które zrobiłem raz przez przypadek) trochę się psuje.

Answer 2

Intensywnie obliczeniowo sposób byłoby przypisanie owoców w sposób okrągły, zaczynając od najwyższej wartości odżywczej dla amelii.
Stamtąd stopniowo przechodź przez owoce z najniższej wartości odżywczej posiadanej przez amelię, i spróbuj każdej kombinacji (a) dając owoc do jessicy, lub (b) zamieniając owoc z tym posiadanym przez Jessica, a jednocześnie spełniając reguła. Następnie zastosuj tę samą metodę do jessica i bruno. Powtórz te 2 pętle, aż nie będzie już możliwe zamiany ani podania.
Nieco trudniejsze, ale potencjalnie szybsze, byłoby jednoczesne oddanie/zamiana na jess/bruno. Na każde 2 kawałki owoców, które posiada A, masz 4 opcje do wypróbowania, a więcej, jeśli jednocześnie spróbujesz zrównoważyć J & B.

Aby uzyskać szybszy algorytm, możesz spróbować zapytać przy stosie matematyki strona wymiany, ponieważ jest to bardzo problem związany z zestawem teorii.