[djKris]

Szukam podpowiedzi jak napisać program (lub z jakiej własności matematycznej skorzystać), który ze zbioru 10 liczb stworzy dwie sumy (po 5 elementów) uwzględniając warunek, iż jedna suma musi być conajmniej 5% większa od drugiej.
(liczby w grupach się nie powtarzają)

Przykład:
Dostępne liczby 1,2,3,4,5,6,7,8,9,10

Podejście numer 1:
GrupaA: 2,4,5,7,9 (suma 27)
GrupaB: 1,3,6,8,10 (suma 28)
GrupaB / GrupaA = 103,7%

Róznica miedzy grupami jest za mała.

Podejście numer 2:

GrupaA: 1,3,6,7,9 (suma 26)
GrupaB: 2,4,5,8,10 (suma 29)
GrupaB / GrupaA = 111,54%

GrupaB jest większa o conajmniej 5% od GrupaA i jest to najmniejsza możliwa różnica spełniająca wymagania.

#programowanie #matematyka #python

[glonstar]

@djKris: Posortuj i weź elementy 1..5 oraz 6..10.

[l.....i]

Posortuj i weź elementy 1..5 oraz 6..10.

@glonstar: mam wrażenie że OP zaraz będzie aktualizował specyfikację problemu (✌ ﾟ ∀ ﾟ)☞

[djKris]

@glonstar:
A: 1+2+3+4+5 = 15
B: 6+7+8+9+10 = 40

B/A = 266,66%

Oczekiwany wynik to coś najbliżej B/A = 105%

[glonstar]

@djKris: Nic nie mówiłeś, że ma być najbliżej. Mówiłeś, że ma się różnić co najmniej o 5%, i się różni.

[l.....i]

@djKris: nie - według twojej specyfikacji każda kombinacja zbiorów pięcioelementowych których suma różni się o więcej niż 5% spełnia warunki zadania

[djKris]

@luzny_lori: nie zdążyłem edytować :D
Dopiszę tutaj:

Szukam podpowiedzi jak napisać program (lub z jakiej własności matematycznej skorzystać), który ze zbioru 10 liczb stworzy dwie sumy (po 5 elementów) uwzględniając warunek, iż jedna suma musi być conajmniej 5% większa od drugiej - szukam takich zbiorów liczb gdzie ta różnica wynosi conajmniej 5% ale musi być jak nabliższa tym 5%.
(liczby w grupach się nie powtarzają)

[l.....i]

@djKris: na to wskazywało ostatnie zdanie, niemniej jednak formalnie nie było to częścią wymagań. co ciekawe - @Pan_Qcek się chyba domyślił bo podesłał całkiem dobry pomysł

[Pan_Qcek]

Posortuj od najwiekszej do najmniejszej i dodawaj kolejno liczby do mniejszej sumy

[selenita66]

@djKris: To brzmi jak klasyczne zadanie sprawdzające podczas rekrutacji. Czyżbyś właśnie przechodził jakiś test online? ;)

[G.....r]

@djKris: bruteforce ( ͡° ͜ʖ ͡°)

[djKris]

@selenita66: wyjątkowo nie :D już mnie przyjęli jakiś dłuższy czas temu i muszę coś ogarnąć

[l.....i]

Posortuj od najwiekszej do najmniejszej i dodawaj kolejno liczby do mniejszej sumy

@Pan_Qcek: i jak różnica jest >= 5% to jesteś w domu, w przeciwnym wypadku właśnie dotarłeś do ciekawszej części zadania (╭☞σ ͜ʖσ)╭☞

[djKris]

"Może i #!$%@? zrobione. Ale szybko. I tanio."

https://repl.it/repls/LumpyFirmExabyte

from itertools import combinations

input = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

allCombs = []
results = []

comb = combinations(input, 5)

for i in list(comb):
allCombs.append(i)

for indexA, itemA in enumerate(allCombs, start = 1):
aaa = itemA
for indexB, itemB in enumerate(allCombs, start = 1):
bbb = itemB

if bool(set(itemA) & set(itemB)) == False:
div = sum(itemA) /

[croppz]

@djKris: fajny kod, szkoda tylko trochę że przy 50 elementach umrę zanim skończy liczyć ( ͡° ͜ʖ ͡°)

[djKris]

@croppz wszyscy wymrzemy...

[w.....a]

przy 50 elementach

@croppz:
Ale elementów jest 10. To tylko binomial(10,5)= 252 sprawdzeń.

Na oko stwierdzam że problem jest NP-zupełny i niestety nawet jak znajdziesz 1000x lepszy algorytm, to przy większej ilości elementów i tak będzie działał latami.

[L.....G]

@djKris: W sumie prosta sprawa.

Sumujesz wszystkie, dostajesz oczywiście sumę ;)
potem obliczasz (chyba nie muszę pisać jak) ile ta mniejsza suma może mieć max.
I sprowadziłeś problem do problemu plecakowego.
Teraz Waga i Wartość to właśnie te liczby. Max waga to wynik który policzyłeś na początku.
I maksymalizujesz wynik(ale nigdy nie przekroczysz tego maxa)

Ta da :)

[L.....G]

@djKris: PS.
A tak z ciekawości, to zadanie ma jakiś praktyczny wymiar? Jeśli to nie tajemnica możesz zdradzić do czego Ci to?