• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Możliwie najmniejsza liczba zbiorów utworzona z danego na wejściu ciągu

VPS Starter Arubacloud
0 głosów
349 wizyt
pytanie zadane 8 października 2021 w Algorytmy przez Beginner555 Obywatel (1,760 p.)
Dzień dobry,

Próbuję stworzyć taki algorytm w języku C++, który rozwiąże takie zadanie:

 

WP: ciąg różnych liczb naturalnych n ( 1 ≤ n ≤ 1000) z przedziału [1,m]( 1 ≤ m ≤ 150 ).

WK: możliwie najmniejsza liczba zbiorów utworzona z danego na wejściu ciągu: 2-elementowych {x,y} pełniąca własność x+y<=m (każdą liczbę należy użyć dokładnie jeden raz). W przypadku, gdy dla zadanej wartości x nie można już znaleźć takiej liczby y, by spełniona była powyższą własność, należy utworzyć zbiór jednoelementowy {x}.

Na wejściu w pliku tekstowym znajdują się dwie liczby n i m oddzielone pojedynczą spacją. W następnych n liniach podane są liczby naturalne, z których należy utworzyć zbiory.

Na wyjściu w pliku tekstowym out.txt w pierwszej linii (i drugiej) linii wypisz minimalną liczbę zbiorów dwu lub jednoelementowych dla pierwszego (i drugiego sposobu). W kolejnych liniach podaj elementy wygenerowanych zbiorów.

Przykład:

in.txt

8 140

60

70

80

56

67

78

81

68

out. txt

5

5

56 81

60 80

78

67 70

68

56 81

60 80

78

67 70

68

Więc mniej więcej rozumiem o co tu chodzi jak wyszedł taki wynik, no może oprócz tych zduplikowanych zbiorów które nie wiem dlaczego tam są. Problem jest również w tym, że nie mam pomysłu jak stworzyć optymalny algorytm, który by tworzył te zbiory. Proszę o jakieś podpowiedzi, może istnieją już jakieś gotowe algorytmy, które rozwiązują takie problemy? Za każdą pomoc szczere DZIĘKUJĘ ;)

2 odpowiedzi

0 głosów
odpowiedź 8 października 2021 przez Wiciorny Ekspert (269,120 p.)
Generalnie wydaje mi sie, że to sformułowanie jest - odzwierciedleniem pewnego problemu zwanego Subset_SUM

https://en.wikipedia.org/wiki/Subset_sum_problem
komentarz 8 października 2021 przez Beginner555 Obywatel (1,760 p.)
To jest jakoś połączone z programowaniem dynamicznym? Mógłby Pan wytłumaczyć mniej więcej jak to wykorzystać w tym zadaniu? Dopiero zaczynam uczyć się algorytmów i jeszcze tego specjalistycznego języka nie rozumiem.
0 głosów
odpowiedź 13 lipca 2022 przez cpp_lover Początkujący (290 p.)

Nie jestem jakimś specialistą, ale zrobiłbym tak:

1.Posortowałbym duży zbiór(najlepiej bąbelkowo)

2.Dobierał najmniejszy z największym, aż ich suma nie będzie większa od m, a resztę zostawiłbym w zbiorach 1-elementowych

3. Policzyłbym zbiory i wypisał jak trzeba.

Akurat się bawiłem z sortowaniem więc masz tutaj: 

int sort(bool k=1){for(int i=0;i<l-1;i++)for(int j=1;j<l-i;j++)if(k==0){if(t[j]>t[j-1])swap(t[j],t[j-1]);}else if(t[j]<t[j-1])swap(t[j],t[j-1]);

t oraz l miałem w klasie, więc trzeba je dorobić

komentarz 13 lipca 2022 przez cpp_lover Początkujący (290 p.)
Oj. Nie zauważyłem daty. )-:

Chyba już nieaktualne
komentarz 13 lipca 2022 przez Wiciorny Ekspert (269,120 p.)
chyba tak i 1.Posortowałbym duży zbiór(najlepiej bąbelkowo) z tą złożonością  tego algorytmu to nie jest to dobre rozwiązanie
komentarz 13 lipca 2022 przez cpp_lover Początkujący (290 p.)
Max 1000 elementów w tym zbiorze, więc dało by radę, ale złożoność obliczeniowa spora niestety. Można by zamiast sortować, to od razu szukać najmniejszego i największego i je parować.

Podobne pytania

0 głosów
0 odpowiedzi 152 wizyt
pytanie zadane 27 maja 2022 w Algorytmy przez Metarinda Użytkownik (740 p.)
0 głosów
1 odpowiedź 294 wizyt
pytanie zadane 21 stycznia 2023 w Algorytmy przez hharry33 Nowicjusz (150 p.)
0 głosów
1 odpowiedź 225 wizyt
pytanie zadane 5 stycznia 2022 w Algorytmy przez shoshana Nowicjusz (120 p.)

92,454 zapytań

141,262 odpowiedzi

319,089 komentarzy

61,854 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Akademia Sekuraka 2024 zapewnia dostęp do minimum 15 szkoleń online z bezpieczeństwa IT oraz dostęp także do materiałów z edycji Sekurak Academy z roku 2023!

Przy zakupie możecie skorzystać z kodu: pasja-akademia - użyjcie go w koszyku, a uzyskacie rabat -30% na bilety w wersji "Standard"! Więcej informacji na temat akademii 2024 znajdziecie tutaj. Dziękujemy ekipie Sekuraka za taką fajną zniżkę dla wszystkich Pasjonatów!

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...