Algoryt doboru elementów tablicy.

Przyszło mi napisać program który, powinen dobierać elementy z tablicy n-ementowej wedle pewnego wzorca. Sytuacje wygląda tak: mamy tablice np. 100 elementową. Każdy z elementów tablicy posiada wartość np n0=0,521, n1=0,522, n3=0,561...n100. Z danej taliby musze wybrać zadaną liczbę elemnetów np k=20. Mam również zadaną wartość śrdnią do którje dążymy np s=0,51. Chodzi o to aby z tablicy n dobrać k elementów takich aby ich średnia była najbardziej zbliżona (bądz równa) zadanej wartości średniej s (0,521).

Czy możecie mi wskazać drogę, czy warto myśleć nad napisaniem algorytmu samemu. Czy może już istnieje algorytm rozwiązujący to zadanie?

Z góry dzięki.

Odejmujesz każdy element od pożądanej wartości średniej, a następnie szukasz podzbioru k-elementowego o sumie równej zero. Jest to uogólniony problem 3SUM czasami nazywany kSUM: http://cs.stackexchange.com/questions/2973/generalised-3sum-k-sum-problem
Edycja: z tą różnicą, że kSUM pyta, czy istnieją elementy dające dokładnie zero, a Ty szukasz elementów dających coś najbliższe zeru. Niemniej pewnie w trakcie wykonywania algorytmu da się zapamiętać minimalną znalezioną różnicę, więc jakieś uogólnienie pewnie jest.

To jest wariacja na temat problemu sumy podzbioru, który jest NP-zupełny. W klasycznym problemie sumy podzbioru masz wskazać podzbiór sumujący się do 0, niemniej sumowanie sie do dowolnej innej liczby jest problemem analogicznym. U ciebie pozbiór ma się sumować do k*średnia. Możemy więc, jak zauważył @Afish, odjąć od każdej liczby średnią i szukać podzbioru sumującego sie do 0.

Nie zmienia to faktu że problem jest NP-zupełny, więc nie znamy algorytmu lepszego niż wykładniczy, testujący wszystkie możliwości.

Dzięki juz mam, dziala świetnie.