logowanie

matematyka » forum » matematyka » temat

Dopasowanie sumy liczb z jak najmniejszą resztą

ostatnie wiadomości  |  regulamin  |  latex

AutorWiadomość

adam_ha
postów: 2
2020-07-29 17:35:39

Witam.
Czy ktoś będzie w stanie pomóc w opracowaniu metody liczenia (algorytmu) doboru elementów.
W przybliżeniu problem wygląda tak:
Mamy 7 rodzajów produktów - 7 długości (w przyszłości może być więcej):
415
324
310
217
208
110
105
Klient podaje łączną długość, którą potrzebuje.
Trzeba ustalić algorytm, który dobierałby odpowiednie długości elementów, ale żeby:
- odpadów było jak najmniej (czyli reszty z dodawania)
- było jak najmniej elementów (jak najmniej połączeń elementów)

Przykład:
Klient podaje długość 966.

Teoretycznie można dać:
a)
415
415
208
i będzie 72 do ścinki
b)
415
310
310
i będzie 69 do ścinki
c)
324
324
324
i będzie 6 do ścinki
d)
324
217
217
217
i będzie 9 do ścinki
e)
324
217
217
208
i nie będzie ścinki (idealna długość)
f)
217
217
217
217
110
i będzie 12 do ścinki
itd.

Możliwości jest dużo, więc metoda "brute force" raczej odpada (dobieranie każdy z każdym elementem i porównywanie wyników)
Przydałby się algorytm dobierania. Ważne jednak, żeby:
- ścinka jak najkrótsza, lub bez ścinki (bez reszty)
- ścinka 30 zastępuje jedno połączenie więcej (tzn. przykład f. ma 5 elementów. Przykłady a. i b. mają po 3 elementy. Skoro w przykładzie f. jest 12 ścinki, to lepszym dopasowaniem byłoby b., ponieważ 12+30+30=72 (o dwa elementy więcej, czyli o 2 połączenia) a w przykładzie b. jest 69.

Ktoś, coś?
Jakieś pomysły jak to ugryźć?
:)


Szymon Konieczny
postów: 9920
2020-09-01 07:50:06

Polecam sortowanie macierzowe. Pierwsza cyfra odkryta, druga zakryta, trzecia odkryta. Rozłożyć na kupki po trzy karty, podzielić kupki na dwie części i mamy pule 1:0. Pisać dalej?



Szymon Konieczny
postów: 9920
2020-09-01 07:53:28

4, 3, To pula Hi, 2, 1 to low


Szymon Konieczny
postów: 9920
2020-09-01 07:56:25

4 liczymy za 11
3 liczy za 10


cyfry 1,2,5,6,7,8,9 liczymy normalnie.

cyfrę zero liczymy Jako sprawdzam


Szymon Konieczny
postów: 9920
2020-09-01 07:58:21

Uczyłem mojego chrześniaka, na kartach w to grać, na prawdę proste, to jest skoro dziecko w czwartej klasie podstawówki, ogarnia macierze


adam_ha
postów: 2
2020-09-01 18:11:08

Dzięki za odpowiedź, ale może mógłbyś mnie nakierować dokładniej?
Trochę pamiętam jeszcze macierze, ale nie za bardzo kumam w jaki sposób sortowanie może mi pomóc w osiągnięciu jak najlepszego wyniku (czyli uzyskania sumy elementów jak najbardziej zbliżonej do długości, jaką podał klient)?
Może jakiś link do stronki, żebym się dokształcił? :)

strony: 1

Prawo do pisania przysługuje tylko zalogowanym użytkownikom. Zaloguj się lub zarejestruj





© 2019 Mariusz Śliwiński      o serwisie | kontakt   drukuj