Podzbiór danego zbioru liczb o zadanej z góry sumie

[Jan_J]

Witam,
staram się w Arkuszu Kalkulacyjnym zrobić mały myczek.
Mam zbiór liczb całkowitych, np. 233 ,200, 1000 ,1001 etc.
Z tego zbioru liczb muszę wyszukać czy jest możliwość osiągnięcia wyniku, 1 000, 2 000, 3 000, 4 000, 5 000, 6 000, 7 000, 8 000, 9 000 lub 10 000
poprzez zsumowanie tych liczb ze zbiór,
mówiąc w skrócie,
czy ze zbioru liczb jest możliwość osiągnięcia z którychś z wyników powyżej wykorzystując tylko i wyłącznie sumowanie niektórych z tych liczb [liczby ze zbioru nie mogą się powtarzać]

np.
chce osiągnąć 1.000
mam zbiór liczb:
500
200
250
300

Ten "mały myczek" ma za zadanie wyszukać możliwości osiągnięcia wyniku 1000 ze zbioru tych czterech liczb i pokazuje wynik:
500 +200 +300 = [da] 1000

Proszę o pomoc

[Jan_J]

Temat nie odpowiadał treści. Zmieniłem.
Temat pasuje bardziej do działu ,,makra i programowanie''. Przeniosłem, chociaż niektóre (mało efektywne) metody rozwiązania zadania da się zrealizować przy użyciu samych tylko formuł.

Temat nie jest związany z użytkowaniem OpenOffice, tylko z algorytmiką. Jakieś książki trzeba w życiu czytać.

Podpowiedź: jest to szczególny przypadek tzw. ,,problemu plecakowego''. Wybór metody zależy od tego, ile tych liczb może być w praktyce.

Aha. Zadań domowych nie rozwiązujemy.

[naye666]

Witam,

dziękuję za poprawę i przeniesienie etc.

Nie to nie zadanie domowe, tych liczb jest 60.
Mam programik napisany w C# przez ojczyma, który robi nieograniczoną danych ze zbioru i sprawdza wszystkie możliwości, ale brak mu optymalizacji i dzięki temu sprawdzenie 51 danych w zbiorze zajmuje bagatela 90tys. lat
Dlatego umówmy się, że takowych liczb jest 60 + niektóre podwójne

[Jan_J]

Hasło: programowanie dynamiczne
Literatura (o ile nie przestraszy): Banachowski, Diks, Rytter: Algorytmy i struktury danych. Cormen, Leiserson, Rivest, Stein: Wprowadzenie do algorytmów.

Wskazówki:

1. Uporządkuj swoje liczby od największej do najmniejszej, pomijając zera. Sprawdź, ile największych składników musisz dodać, by osiągnąć lub przekroczyć wymaganą sumę.
Twój zbiór musi się składać z co najmniej tylu liczb. Niech to będzie N.
(Sumując liczby ,,od końca'' dostaniesz górne oszacowanie ilości niezbędnych składników. Niech to będzie NMax. Przyda się tylko do szacowania ilości podzbiorów.)

2. Wygeneruj (zapamiętując je w jakiejś strukturze) wszystkie podzbiory N-elementowe, sprawdzaj ich sumy. Jak się zgodzi z wymaganiem, to koniec.

3. Jeżeli żadna suma się nie zgodzi, łącz posiadane podzbiory w większe, sprawdzając ich sumy i zapamiętując na przyszłość te, które nie dają zbyt dużej sumy. A jak któraś suma się zgodzi, to koniec.
(Po drodze są delikatne momenty: 1. łączone podzbiory mogą mieć część wspólną, 2. jak nie pomieszać ze sobą starych i nowych podzbiorów, 3. jak uniknąć powtórzeń połączonych podzbiorów). Rob to tak długo, aż nie trafisz lub aż na danym ,,piętrze'' podzbiorów nie dostaniesz tylko za dużych sum (tj. lista ,,obiecujących'' podzbiorów się opróżni).

4. Jeżeli żaden sprawdzony podzbiór nie miał dokładnie takiej sumy jaką chcesz, to znaczy że takiego podzbioru nie ma. Też koniec.

Z wyjątkiem bardzo krótkich ciągów liczb, problem jest zbyt poważny, by atakować go arkuszem. Wymaga programowania.

Zgrubne (na ogół pesymistyczne) szacowanie ilości operacji dostaniesz sumując liczbę wszystkich podzbiorów K-elementowych, gdzie K zmienia się do N do NMax.

Realnych czas wykonania bywa bardzo rozmaity. Dla 500 losowo wybieranych liczb z przedziału od 0 do 100, i dla sumy 10000, dostaję w interpreterze na ogół czasy rzędu od kilku do kilkudziesięciu sekund (co oznacza, że rozwiązanie znaleziono gdzieś w drugiej lub na początku trzeciej fazy algorytmu). Oczywiście, dla szczególnych danych może też być dużo gorzej. I bywa -- bo faza trzecia może wymagać przejrzenia wielkiej liczby podzbiorów. Bywa też, że rozwiązanie nie istnieje.

[naye666]

Dziękuję za literaturę + objaśnienie problemu, faktycznie może to się udać, dziękuję raz jeszcze biorę się do roboty. Pozdrawiam.