Suma dowolnych liczb = 30, ze zbioru liczb n

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
Zmienna
Użytkownik
Użytkownik
Posty: 2
Rejestracja: 9 gru 2009, o 20:00
Płeć: Kobieta
Lokalizacja: Polska

Suma dowolnych liczb = 30, ze zbioru liczb n

Post autor: Zmienna »

Witam!

To mój pierwszy post na tym forum i nie jestem pewna, czy moje pytanie umieszczam we właściwym dziale.

Problem, który próbuję rozwiązać, to nie jest zadanie do szkoły, na uczelni - naukę skończyłam już dosyć dawno temu , ale człowiek w końcu uczy się przez całe życie.

Próbuję podejść jakoś do takiego problemu:
1) Mam dane różne liczby w zbiorze, np.: 2, 5, 9, 7, 11, 3, 14, 20, 19, 1.
2) Potrzebuję wybrać z tego zbioru jak najmniejszą liczbę podzbiorów liczb (dowolna ilość liczb w tym podzbiorze), która dałaby w sumie wartość \(\displaystyle{ \le}\)30 (jak najbliższe liczbie 30).

Czyli, np. z powyższych liczb można wyłonić zbiory: (11, 19), (20, 7, 3), (2, 5, 9, 14) i pozostaje liczba 1.
Z pewnością można wybrać też inne podzbiory.
Mnie interesowałoby wybranie liczb tak, aby było jak najmniej podzbiorów i najlepiej, aby została maksymalnie jedna liczba niewybrana, z całego zbioru liczb.

Umieściłam mój post w tym dziale, bo wydaje mi się, że być może jakoś można by było zastosować do tego kombinacje? permutacje? wariacje?
Tylko nie wiem, jak zoptymalizować takie wyszukiwanie?
Mogę wypisywać wszystkie układy, jakie przyjdą mi do głowy, ale chciałabym to jakoś usprawnić.

Proszę o pomoc, czy da się jakoś to "ugryźć"?
Być może taki temat już był, ale według przeze mnie wpisywanych fraz - nic nie znalazłam.
Jeśli temat był już rozważany, to proszę o link lub jakiekolwiek inne wskazówki (np. na jaką frazę szukać rozwiązania).
Awatar użytkownika
Pinki1983
Użytkownik
Użytkownik
Posty: 43
Rejestracja: 6 gru 2009, o 16:20
Płeć: Mężczyzna
Lokalizacja: Polska
Pomógł: 8 razy

Suma dowolnych liczb = 30, ze zbioru liczb n

Post autor: Pinki1983 »

To jest zadanie wg z zakresu informatyki a dokładniej z optymalizacji, nie wiem czy Zmiennej chodzi o napisanie algorytmu jak to zrobić, bo jeśli tak to idea jest w miarę prosta, a jeśli to nie o to chodzi to nie wiem o co...
Zmienna
Użytkownik
Użytkownik
Posty: 2
Rejestracja: 9 gru 2009, o 20:00
Płeć: Kobieta
Lokalizacja: Polska

Suma dowolnych liczb = 30, ze zbioru liczb n

Post autor: Zmienna »

Pinki1983, owszem, chodzi o algorytm, ale wydaje mi się, że nie byłoby to takie proste, tzn. jak znaleźć wszystkie możliwe rozwiązania i móc wybrać z nich najbardziej optymalne.
Nawet zastanawiałam się, czy nie dałoby się tego zrobić excelowym Solverem, ale nie wiem, czy to się dałoby w ogóle tak zastosować.
Jeśli masz jakąś sugestię Pinki1983, to podziel się ze mną!
Awatar użytkownika
Pinki1983
Użytkownik
Użytkownik
Posty: 43
Rejestracja: 6 gru 2009, o 16:20
Płeć: Mężczyzna
Lokalizacja: Polska
Pomógł: 8 razy

Suma dowolnych liczb = 30, ze zbioru liczb n

Post autor: Pinki1983 »

Ale co jest ważniejsze żeby liczba tych zbiorów była najmniejsza czy żeby "użyć wszystkich elementów"?
Mam pewien pomysł, ale to zależy co jest ważniejsze.
ODPOWIEDZ