Witam, mam oto następujący problem.
Mając zbiór dziewięciu liczb naturalnych (niekoniecznie różnych) pogrupować je w takie trójki \(\displaystyle{ X=(x_1,x_2,x_3)}\), \(\displaystyle{ Y=(y_1,y_2,y_3)}\), \(\displaystyle{ Z=(z_1,z_2,z_3)}\) aby suma każdej z trójek była możliwie jak największa.
Trywialny przykład dla zobrazowania:
Niech \(\displaystyle{ \{1,1,1,1,1,1,1,1,2\}}\)będzie zadanym zbiorem, wtedy \(\displaystyle{ X=(1,1,1)}\); \(\displaystyle{ Y=(1,1,1)}\), \(\displaystyle{ Z=(1,1,2)}\). Mamy dwie sumy równe \(\displaystyle{ 3}\) i jedną równą \(\displaystyle{ 4}\). Zresztą każde rozłożenie daje te sumy, czyli jest to poprawne rozwiązanie.
Maksymalizacja pewnych sum
-
madmathman
- Użytkownik
- Posty: 89
- Rejestracja: 19 lut 2015, o 20:22
- Płeć: Mężczyzna
- Lokalizacja: katowice
- Podziękował: 30 razy
-
Medea 2
- Użytkownik
- Posty: 2491
- Rejestracja: 30 lis 2014, o 11:03
- Płeć: Kobieta
- Podziękował: 23 razy
- Pomógł: 479 razy
Maksymalizacja pewnych sum
Ale jaki jest porządek? Na przykład dla dziewiątki \(\displaystyle{ {0, 2, 2, 3, 3, 3, 3, 4, 5}}\) łatwo wskazać dwa rozkłady na sumy \(\displaystyle{ 7+9+9}\) i \(\displaystyle{ 8+8+9}\). Który jest lepszy?
-
madmathman
- Użytkownik
- Posty: 89
- Rejestracja: 19 lut 2015, o 20:22
- Płeć: Mężczyzna
- Lokalizacja: katowice
- Podziękował: 30 razy
Maksymalizacja pewnych sum
Niech \(\displaystyle{ A=\{a_1,\ldots,a_9\}}\). Mamy dwa rozkłady uporządkowane w następujący sposób:
\(\displaystyle{ X_1}\), \(\displaystyle{ Y_1}\), \(\displaystyle{ Z_1}\)
oraz
\(\displaystyle{ X_2}\), \(\displaystyle{ Y_2}\), \(\displaystyle{ Z_2}\)
Przyjmujemy, że suma liczb z \(\displaystyle{ X_1}\) jest mniejsza bądź równa od sumy liczb z rozkładu \(\displaystyle{ Y_1}\);a z kolei ta suma jest mniejsza bądź równa sumie liczb z \(\displaystyle{ Z_1}\); analogicznie dla drugiego rozkładu (indeks dolny równy dwa).
Rozkład pierwszy będzie "lepszy", gdy suma w\(\displaystyle{ X_1}\)jest większa bądź równa od sumy w \(\displaystyle{ X_2}\) oraz tak samo dla pozostałych trójek. Jeżeli taki rozkład nie istnieje to wybieramy możliwą największą sumę \(\displaystyle{ Z_1}\) i podane kryterium rozpatrujemy dla trójek \(\displaystyle{ X}\) i \(\displaystyle{ Y}\).-- 24 cze 2015, o 15:41 --Ewentualnie mogę wyliczyć średnią i odpowiednie sumy zbliżać jak się da to tej średniej. To wydaje mi się najbardziej rozsądne.
\(\displaystyle{ X_1}\), \(\displaystyle{ Y_1}\), \(\displaystyle{ Z_1}\)
oraz
\(\displaystyle{ X_2}\), \(\displaystyle{ Y_2}\), \(\displaystyle{ Z_2}\)
Przyjmujemy, że suma liczb z \(\displaystyle{ X_1}\) jest mniejsza bądź równa od sumy liczb z rozkładu \(\displaystyle{ Y_1}\);a z kolei ta suma jest mniejsza bądź równa sumie liczb z \(\displaystyle{ Z_1}\); analogicznie dla drugiego rozkładu (indeks dolny równy dwa).
Rozkład pierwszy będzie "lepszy", gdy suma w\(\displaystyle{ X_1}\)jest większa bądź równa od sumy w \(\displaystyle{ X_2}\) oraz tak samo dla pozostałych trójek. Jeżeli taki rozkład nie istnieje to wybieramy możliwą największą sumę \(\displaystyle{ Z_1}\) i podane kryterium rozpatrujemy dla trójek \(\displaystyle{ X}\) i \(\displaystyle{ Y}\).-- 24 cze 2015, o 15:41 --Ewentualnie mogę wyliczyć średnią i odpowiednie sumy zbliżać jak się da to tej średniej. To wydaje mi się najbardziej rozsądne.