Jak obliczyć sumę wszystkich liczb?

[ViPhone]

Cześć, szukam programu, w którym przykładowo podam 10 liczb, i zostanie mi wyświetlona suma każdej kombinacji tych liczb, czyli np.:

1. 10
2. 20
3. 15
4. 5

Program podaje więc wyniki działań 10+20, 10+20+15, 10+20+15+5, 10+15, 10+5, 10+20+5 itd., czyli każdą możliwą kombinację sumuje. Firma "Amino" zrobiła konkurs w chińskich zupkach, w opakowaniu drukują liczbę z przedziału 1-1000, i jeśli znajdziemy kombinację, która da nam równo 100, 200, 300, 400, 500, 600, 800 800, 900 lub 1000 złotych, to taką sumę wygrywamy
Problem pojawia się, kiedy mam 20-kilka takich liczb, i liczenie każdej możliwości zajęłoby wieki (a przynajmniej dla mnie, gdzie czas jest ważny).

[kalwi]

ale pytasz się o gotowy okienkowy program do ściągnięcia i uruchomienia, czy o kod w jakimś języku do stworzenia go?

[Althorion]

Problem pojawia się, kiedy mam 20-kilka takich liczb, i liczenie każdej możliwości zajęłoby wieki (a przynajmniej dla mnie, gdzie czas jest ważny).

Zagadnienie znalezienia podzbioru o ustalonej sumie jest NP-zupełne, tak więc nie oczekuj szybkich wyników, nawet przy wykorzystaniu maszyn liczących.

[ViPhone]

Okienkowy program, lub chociażby kod do skompilowania, wszystko jedno. A co do szybkich wyników - dla 50 liczb, wynik chociażby przeliczany przez CPU/GPU w ok. godzinę czy dwie jest dużo bardziej postępowy od liczenia tego w głowie. Pytałem chłopaków na forum PHP o taki skrypt, ale podobno dużo pisania jest, i nikt się nie chce tego podjąć za frajer, a płacić przecież nie będę, bo do życia mi to niezbędne nie jest. Mimo wszystko szukam - na 100% musi być jakiś substytut tego pomysłu wykonany niekoniecznie w PHP, który spełni swoją rolę. A że na tym forum najbardziej utożsamiacie się właśnie z cyferkami, to i tutaj postanowiłem zasięgnąć porady

[Althorion]

Skrypt w Pythonie 3, napisany na szybko, więc bez myślenia o wydajności itd.:

Kod: Zaznacz cały

import itertools

input_data = (50, 40, 10, 60, 80, 110) # Tu wpisz dane do obliczeń

for i in range(2, len(input_data)+1):
    for combination in itertools.combinations(input_data, i):
        s = sum(combination)
        if 100 <= s <= 1000 and s % 100 == 0:
            print(combination, ": ", s, " zł", sep="")

Dla tamtych przykładowych danych daje wynik:

Kod: Zaznacz cały

(40, 60): 100 zł
(50, 40, 10): 100 zł
(50, 40, 110): 200 zł
(10, 80, 110): 200 zł
(50, 10, 60, 80): 200 zł
(50, 60, 80, 110): 300 zł
(40, 10, 60, 80, 110): 300 zł

Przerobienie programu tak, by wyświetlał tylko najwyższe możliwe sumy pozostawiam jako ćwiczenie dla czytelnika .

[kalwi]

ViPhone, napisz tutaj te liczby, bo chyba mogę mieć rozwiązanie.

[musialmi]

Gościu ma nick Vifon i pisze o zupkach Amino - on wcale nie szuka pomocy, tylko po prostu chce nakręcić rynek zupek chińskich!

[ViPhone]

@UP: Tak, masz rację, haha
Po prostu mi się tak wymyśliło przy rejestracji na szybko, lubię takie słowne gierki
Z resztą to dwie osobne firmy, więc gryzłoby się to ze sobą.

@Althorion: Dzięki wielkie bracie, jutro na spokojnie sobie to odpalę, pewnie wypali

@kalwi: Nie mam teraz jak sprawdzić, bo w robocie siedzę, ale to są liczby z przedziału 1-1000, zupełnie przypadkowe, tj. 191, 325, 52, 78 (akurat te pamiętam).

Edit: 18:27

@Althorion: Niestety, nie zdaje to egzaminu. Owszem, printuje mi wyniki (te które podałeś jako przykładowe), ale to nie jest suma wszystkich liczb które podałem. Nie znam pythona, więc mam prośbę - mógłbyś to "naprawić"? Zamysł dobry, ale większości wyników brak.

Jeszcze inny edit:

Dobra, już załapałem! Skrypt podaje tylko wyniki, które są równe pełnym setkom! Okej, dzięki wielkie, teraz wszystko gra i buczy

[BlancaSalvatore]

Hej!
Mam zapytanie, bo z racji tego, że jestem beznadziejna w pisaniu w Pythonie, mógłby mi ktoś krok po kroku wytłumaczyć jak to rozkimnić?
Z góry dzięki

[Althorion]

Jasne. Co chcesz „rozkminić”?

[BlancaSalvatore]

To co kolega wyżej, jak kto napisać, żeby t te równe kwoty z podanych obliczało
Problem polega na tym, że całkowicie nie rozumiem tego programu i nie umiem czegoś takiego napisać, nawet to jak to wytłumaczyłeś wcześniej jest dla mnie niezrozumiałe... :/

[Althorion]

Wytłumaczenie działania, linijka po linijce:

Kod: Zaznacz cały

import itertools

input_data = (50, 40, 10, 60, 80, 110) # Tu wpisz dane do obliczeń

for i in range(2, len(input_data)+1):
    for combination in itertools.combinations(input_data, i):
        s = sum(combination)
        if 100 <= s <= 1000 and s % 100 == 0:
            print(combination, ": ", s, " zł", sep="")

1. Importuje bibliotekę

Kod: Zaznacz cały

https://docs.python.org/dev/library/itertools.html

, która jest fragmentem biblioteki standardowej Pythona (więc można być pewnym, że jeśli jest Python, to jest i ona), będę z niej korzystać do wygenerowania wszystkich możliwych kombinacji.
3. Krotka zawierająca liczby całkowite używane w programie, nazwana input_data.
5. Główna pętla, idąca od dwójki do długości krotki z danymi; ta liczba będzie mi potrzebna jako zadana długość generowanych kombinacji. Iterator nazwany jest i.
6. Pętla wewnętrzna. Wykorzystuję funkcję

Kod: Zaznacz cały

https://docs.python.org/dev/library/itertools.html#itertools.combinations

z wyżej wymienionej biblioteki do wygenerowania wszystkich kombinacji danych wejściowych (input_data) o długości i (czyli, jak wiemy z punktu 5., coraz dłuższych, od dwuelementowych do całej listy) i iteruję po niej, nazywając iterator combination.
7. Liczy sumę kombinacji combination, przypisuję tę wartość zmiennej s
8. Jeśli wartość tej sumy jest z przedziału od stu do tysiąca, zaś sama wartość jest podzielna przez sto, wykonuję punkt dziewiąty…
9. …czyli drukuję na ekranie tę kombinację wraz z jej sumą.

Czy któryś z punktów wymaga dodatkowego wyjaśnienia? Coś jest niejasne? Czegoś nie zawarłem?

Dodam też, że ten program był pisany „byle był”, bez przykładania się i mocno niechlujnie, przez co nie stanowi on raczej zbyt dobrego materiału do analizy.