Algorytm grupowania zbiorów

0

Witam,

Piszę program i muszę pogrupować zbiory a nie wiem jaki algorytm będzie do tego najlepszy. Sprawa wygląda tak, że mam n zbiorów o określonej liczebności. Muszę te zbiory połączyć w m nowych zbiorów (oczywiście m<n) tak aby ich wielkość była jak najbliższa sobie, czyli pogrupować równomiernie. Załóżmy że mamy 6 zbiorów o liczebności odpowiednio 6,8,15,24,18,31 i muszę pogrupować je w 3 "równomierne" zbiory. Liczebność wszystkich zbiorów to 102. Chce mieć 3 równe zbiory czyli liczebności oscylującej wokół 102/3=34.
Czy może mi ktoś poradzić jakim najprosztszym algorytmem można to zrobić. Dodam, że tych zbiorów nie będzie jakoś niesamowicie dużo. między np: 5 - 25.
Będę wdzięczny za podpowiedź...Moze ktoś pisał podobny kod....
Dzięki i pozdrawiam

0

Podałeś trochę za mało konkretów. Zbiory można reprezentować na setki sposobów od prostych list elementów po struktury drzewiaste. Ponieważ zależy ci na prostocie reprezentuj zbiór jako tablice elementów. Jak wygląda algorytm? Dokładnie tak jak go przedstawiłeś - konkatenujesz ze sobą wszystkie tablice, powiedzmy do tablicy arrays, następnie obliczasz liczność size jaką będzie miał każdy z nowych zbiorów (być może oprócz ostatniego) i odkrajasz z arrays kawałki liczności size. Z tego co pamiętam C# udostępnia dużo metod manipulujących ciągami typu intersect, concat, copy itp. przez co cały problem można rozwiązać w paru linijkach kodu.

0

Mi to wygląda na wariację problemu plecakowego.

0
Wibowit napisał(a)

Mi to wygląda na wariację problemu plecakowego.

Faktycznie nie dodałem, że zbiorów podstawowych nie można dzielić :( Też mi to podchodziło pod plecakowy ale nie jest to
dokładnie to o co mi chodzi. Zbiory nie mają tu żadnych wag. Poza tym wszystkie muszą być wykorzystane...

1 użytkowników online, w tym zalogowanych: 0, gości: 1