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

Question

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Ę ;)

Answer 1

Generalnie wydaje mi sie, że to sformułowanie jest - odzwierciedleniem pewnego problemu zwanego Subset_SUM

https://en.wikipedia.org/wiki/Subset_sum_problem

Comments

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.

Answer 2

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ć

Comments

Oj. Nie zauważyłem daty. )-:

Chyba już nieaktualne

---

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

---

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ć.