Podział zbioru na możliwie równe podzbiory.

Witam

Mam taki oto problem za który nie wiem jak się zabrać:

Mamy uszeregowany zbiór. Każdy z elementów ma swoją długość. Problemem jest taki podział tego zbioru, żeby uzyskać 4 podzbiory o sumie długości jego elementów jak najbardziej zbliżonej do siebie. Nie możemy zmieniać kolejności elementów, nie możemy rozbijać elementów na elementy o mniejszych długościach. Całość chciałem zaimplementować w php.

Jak wyszukać jak najbardziej optymalne rozwiązanie tego problemu?

Próbujesz niby matematycznie, ale licho ci to idzie...

1. Uszeregowanie tych elementów jest względem czego? Długości? Czy po prostu chodzi o to że masz zadaną kolejność elementów?
2. Zbiory generalnie nie maja czegoś takiego jak kolejność. To mają ciągi.

Moja szklana kula mówi że: Mamy pewien skończony ciąg liczbowy i chcemy znaleźć 3 punkty podziału, które przetną ten ciąg na fragmenty, takie że suma elementów w każdym fragmencie ma być jak najbardziej zbliżona do sumy z pozostałych fragmentów. Tak?

Warto by też sprecyzować kryterium "możliwej równości". Który z dwóch rozkładów liczby 10 jest lepszy: 2+2+2+4 czy 1,5+2+3+3,5?

Shalom napisał(a):

Moja szklana kula mówi że: Mamy pewien skończony ciąg liczbowy i chcemy znaleźć 3 punkty podziału, które przetną ten ciąg na fragmenty, takie że suma elementów w każdym fragmencie ma być jak najbardziej zbliżona do sumy z pozostałych fragmentów. Tak?

Dokładnie tak.

bogdans napisał(a):

Warto by też sprecyzować kryterium "możliwej równości". Który z dwóch rozkładów liczby 10 jest lepszy: 2+2+2+4 czy 1,5+2+3+3,5?

Długość elementu jest wartością całkowitą, lepszy będzie 2+2+2+4

Przykład:

Mamy ciąg: 2, 5, 7, 6, 1, 2, 4 Optymalny podział powinien wyglądać tak:
1 podciąg: 2, 5
2 podciąg: 7
3 podciąg: 6, 1
4 podciąg: 2, 4

Ja bym to zrobił tak Sumujesz "długości" elementów zbioru (u ciebie wyszło mi 27), tą sumę dzielisz na 4 (6.75), i potem idąc od początku dodajesz dopóki nie przekroczysz tej sumy (jak tak to sprawdzasz czy bliżej będzie z elementem czy bez), i masz 1 część. pozostałe 2 ustalasz tak samo tylko zaczynając dodawać od elementu po końcu poprzedniej, a to co ci zostanie idzie do 4. Oczywiście na końcu można sprawdzić czy przesunięcie granicy o jedną liczbę nie poprawi podziału jako całości, zwłaszcza sumy w ostatnim zbiorze bo tam nie sumujemy.

@mascom, nadal nie sprecyzowałeś kryterium. Ja widzę co najmniej trzy naturalne kryteria. Niech a,b,c i d oznaczają sumy, s jest średnią s=(a+b+c+d)/4.

1. minimalizujemy max(a,b,c,d)-min(a,b,c,d),
2. minimalizujemy |a-s|+|b-s|+|c-s|+|d-s|,
3. minimalizujemy (a-s)²+(b-s)²+(c-s)²+(d-s)².