Wyznaczenie zbiorów liczb, któych sumaryczna moc zbiorów wynosi n

Witam,
Mam do dyspozycji pewną liczbę "n" ( 1 <= n <= 100 ), która jest podawana na wejściu.

Dalej mam "m" pewnych kombinacji liczb ( 1 <= m <= 100 ) grupami np. {2,2}, {1,2}, {4,9}, {22,1} które mogę dowolnie zmieniać i następnie generować oczekiwany wynik, czyli w sumie można powiedzieć że też są to dane wejściowe ;)

Następnie z tych "m" grup zbiorów muszę wybrać jak najmniej zbiorów tak aby ilość liczb ze zbiorów wynosiła CO NAJMNIEJ "n", czyli wartości liczb w zbiorach są nie ważne w tym przypadku.

Dam wam przykład bo mogłem namieszać trochę :)

Jedną grupę liczb można wziąć tylko raz!

A więc dla n=10 i m=5 mamy takie coś:

n=10 , czyli musimy wybrać jak najmniej grup liczb z m grup tak aby ilość cyfr z grup wynosiła co najmniej n=10 czyli n>=10 ale najlepiej co najmniej czyli 10 ;)

m=5 czyli mamy 5 grupy liczb spośród których mogę wybierać

{4, 2, 6, 1, 6, 2, 1} - moc zbioru = 7
{2,3,9,1,5,77,2,1,2} - moc zbioru = 9
{2,8,1} - moc zbioru = 3
{1,2} - moc zbioru = 2
{4,2,9,11} - moc zbioru = 4

Czyli optymalne rozwiązanie tutaj to pierwszy(7) + trzeci(3) zbiór liczb bo daje nam 10 liczb czyli co najmniej "n"

co najmniej lub co najwyżej - nie wiem czy dobrze użyłem tego sformułowania w zadaniu ale chodziło mi o to że liczba ma być jak najbliżej n z wykorzystaniem jak najmniejszej grupy liczb

I tutaj pojawia się problem bo rozwiązanie zadania polega na zaimplementowaniu rozwiązania dokładanego zadanego problemu oraz rozwiązania przybliżonego.

Proszę o nakierowanie mnie w którą stronę iść aby rozwiązać ten problem, bo już nie mam pomysłów a zadanie jest podobno "bardzo łatwe".

Dzięki za pomoc Panowie, pozdrawiam :)

Czy jest ktokolwiek w stanie mi pomóc z tym zadaniem ? Próbowałem je zrobić ale nie wychodzi mi, zamieszczenie moich obliczeń nie ma sensu bo są bez sensu, próbowałem jakoś to ogarnąć na grafach ale nie trzyma się kupy to nic. Bardzo proszę o pomoc... Dziękuje za poświęcony czas.

1. Ale moc tego złożonego zbioru ma byc >=n czy suma mocy zbiorów wejściowych? Bo to jest różnica, w kwestii tego czy to multizbiór czy nie. Tzn czy jak złożę zbiory:
   {1,2} i {2,3} to mam moc w sumie 4, czy 3 (bo wynikowy zbiór to {1,2,3} o mocy 3)
2. Jeśli jest to obojętne to chyba sobie robisz jaja z nas, bo te zbiory wejściowe mozesz sobie zamienić na ich moc i potem rozwiązać ten problem za pomocą algorytmu wydawania reszty (wersji dynamicznej).

Shalom napisał(a)

1. Ale moc tego złożonego zbioru ma byc >=n czy suma mocy zbiorów wejściowych? Bo to jest różnica, w kwestii tego czy to multizbiór czy nie. Tzn czy jak złożę zbiory:
   {1,2} i {2,3} to mam moc w sumie 4, czy 3 (bo wynikowy zbiór to {1,2,3} o mocy 3)
2. Jeśli jest to obojętne to chyba sobie robisz jaja z nas, bo te zbiory wejściowe mozesz sobie zamienić na ich moc i potem rozwiązać ten problem za pomocą algorytmu wydawania reszty (wersji dynamicznej).

Faktycznie zapomniałem o tym napisać, a to jest bardzo ważne, przepraszam :P

Oczywiście jest tak jak napisałeś, czyli w przypadku zbiorów {1,2} i {2,3} wynik to zbiór o mocy 3 z elementów {1,2,3}, a więc zadanie nie jest aż tak proste ;)

To zadanie jest totalnie zryte jak dla mnie, a na dodatek trzeba to rozwiązać "dokładnie i w przybliżeniu", masakra...

Czy masz jakiś pomysł jak można by rozwiązać ten problem ?

Dzięki za pomoc!

Jak dla mnie to nadal można zastanowić się nad algorytmem wydawania reszty, tylko trzeba go odpowiednio skomplikować ;d

Shalom napisał(a)

Jak dla mnie to nadal można zastanowić się nad algorytmem wydawania reszty, tylko trzeba go odpowiednio skomplikować ;d

Jeżeli możesz to bardzo prosiłbym o rozwinięcie myśli o skomplikowaniu - na czym ma polegać koncepcja tego podejścia, z chęcią bym skomplikował jeżeli pozwoli mi to dojść do rozwiązania problemu :P

Ok. Musiałbyś po prostu rozpatrywać każdy "nominał" osobno, tzn zbiory {1,2,3} i {2,3,4} oba mają moc 3, ale traktujemy je zupełnie osobno. No i dodatkowo będziesz miał znacznie więcej ścieżek optymalnych (bo klasycznie masz tylko jedną bo nominał o danej wartości masz jeden, a tu mozesz mieć ich wiele).

Shalom napisał(a)

Ok. Musiałbyś po prostu rozpatrywać każdy "nominał" osobno, tzn zbiory {1,2,3} i {2,3,4} oba mają moc 3, ale traktujemy je zupełnie osobno. No i dodatkowo będziesz miał znacznie więcej ścieżek optymalnych (bo klasycznie masz tylko jedną bo nominał o danej wartości masz jeden, a tu mozesz mieć ich wiele).

A jak to zadanie jest najlepiej rozłożyć na grafie i jak uwzględnić Twoją myśl w tym grafie ?

Wydaje mi się, że można zrobić to poprawnie w ten sposób, że waga krawędzi będzie reprezentować "naszą (specyficzną) moc zbiorów" czyli np. 3, gdy w jednym wierzchołku będą następujące liczby {1,2,3}, a w drugim {2,3,4}. No i z danych wejściowych utworzymy taki graf, ale co potem... jak rozwiązać to "dokładnie i w przybliżeniu ? Drugi problem to taki, że ten graf będzie bardzo rozbudowany bo każdy wierzchołek będzie musiał być połączony z drugim wierzchołkiem, czy taki pomysł ma sens ? Na czym to "dokładnie i w przybliżeniu" polega w tym konkretnym przypadku ? Jak przechodzić po grafie dla tego problemu ?

Aha, dobrze wspomniałeś że optymalnych rozwiązań może być kilka, ale wystarczy jak na wyjściu podam jedno optymalne - nie muszę podać wszystkich ;)

Jak dla mnie pomysł z grafem jest bez sensu, bo nic ci ta reprezentacja nie daje i nie uwzględnia dublowania liczb w zbiorach.
Jeśli chodzi o rozwiązanie przybliżone to można je też załatwić algorytmem wydawania reszty:

• ignorujemy dublowanie się liczb i wyznaczamy sobie zbiory trochę "na jana"
• wyrzucamy ze zbioru wynikowego powtarzające się liczby i powtarzamy to aż nam wyjdzie >=n

Shalom napisał(a)

Jak dla mnie pomysł z grafem jest bez sensu, bo nic ci ta reprezentacja nie daje i nie uwzględnia dublowania liczb w zbiorach.
Jeśli chodzi o rozwiązanie przybliżone to można je też załatwić algorytmem wydawania reszty:

• ignorujemy dublowanie się liczb i wyznaczamy sobie zbiory trochę "na jana"
• wyrzucamy ze zbioru wynikowego powtarzające się liczby i powtarzamy to aż nam wyjdzie >=n

Nie odpisywałem od razu w temacie, bo chciałem przemyśleć ten problem, a pojawiły się nowe wątpliwości, a więc...

1.
Jeżeli chodzi o Algorytmy aproksymacyjne to dotychczas realizowane jako przykłady były robione wszystkie na grafach chociażby tj. problem komiwojażera. Ty napisałeś, że graf jest tutaj zbędny, a więc jak przechowywać dane wejściowe i informacje o połączeniach "każdy wierzchołek z każdym" ?

2.
Pierwsze rozwiązanie jakie mam uzyskać to za pomocą rozwiązania dokładnego (optymalnego). Nie mam pojęcia... wizualizowałem sobie to na przykładzie grafu, tak by wykorzystać techniki powrotu ale bez skutku, jakieś pomysły w tej kwestii ?

3.
O przybliżonym napisałeś coś powyżej, ale... Napisałeś wyznaczamy sobie wzory, miałeś na myśli moc zbiorów, tak ? ;) Tylko tutaj pojawia się problem z pierwszego podpunktu z tego posta. Wyznaczam moce zbiorów dla każdego przypadku powiedzmy niech to będzie dwuwymiarowa tablica struktur gdzie np. odwołanie się do pola komórki [4][2] zawiera "naszą moc zbioru bez dublowania" dla zbioru nr. 4+1=5 oraz dla zbioru 2+1=3 (+1 ze względu na liczenie od 0).

Wtedy mam wypełnioną całą tablicę i mogę ją przejść szukając wartości, która jest równa lub najbliżej n. Tylko czy takie rozwiązanie ma cokolwiek wspólnego z rozwiązaniem przybliżonym, jak dla mnie to chyba cieniutko coś :) Bo najpierw musimy wypełnić tablicę dla w danych wejściowych, a następnie wykonać w^2 operacji elementarnych dla wypełnienia tablicy, a potem znowu przejść tą tablicę od początku... no lepiej byłoby chyba podczas wypełniania sprawdzać warunek, ale czy to w ogóle ma sens "algorytmiczny" ? A po drugie pojawia się pytanie w kwestii kiedy jest granica przybliżenia i czy aktualnie uzyskana wartość jest wystarczająca. Trzyma się to jakoś kupy, to co napisałem ?

Jeżeli łaska to bardzo bym prosił o trochę więcej konkretów które przybliża mnie do implementacji algorytmu, bo deadline mi się zbliża nieubłaganie ;)

Dzięki wielkie za poświęcony dla mnie czas! :)

Pozdrawiam, Jerzy

Ja bym porzucił pomysł wciskania tutaj grafu na siłę, bo zwyczajnie nijak tu nie pasuje. Ja tu nie widzę żadnych wierzchołków, bo nie rozumiem co ci daje tutaj niby reprezentacja grafowa. Z komiwojażerem co innego, bo tamten problem jest ewidentnie grafowy ;]
Optymalne rozwiązanie opisałem już przecież powyżej (co nie znaczy że jest dobre, bo ma dużą złożoność i może da się prościej):

• korzystamy z uogólnionego algorytmu wydawania reszty: każdy zbiór przedstawia nam jeden nominał. Wartość nominału stanowi moc zbioru. Oczywiście dwa zbiory o tej samej mocy, ale róznych elementach zbioru są róznymi zbiorami! Następnie wykonujemy kroki algorytmu wydawania reszty tak jak zawsze, ale musimy robić tutaj rekurencję tak aby rozpatrywać wszystkie możliwości wykorzystania zbiorów o tej samej mocy. Dodatkowo zawsze musimy pamiętać o tym żeby sprawdzać moc połączonego zbioru (aktualnego z tym który rozpatrujemy) a nie sumę mocy obu zbiorów.

Przy czym proponuje mieć na uwadze to że może być znacznie łatwiejsze i sensowniejsze rozwiązanie :P Proponuje pomyśleć nad redukcją tego problemu do jakiegoś innego znanego problemu o podobnych własnościach.

Shalom napisał(a)

Ja bym porzucił pomysł wciskania tutaj grafu na siłę, bo zwyczajnie nijak tu nie pasuje. Ja tu nie widzę żadnych wierzchołków, bo nie rozumiem co ci daje tutaj niby reprezentacja grafowa. Z komiwojażerem co innego, bo tamten problem jest ewidentnie grafowy ;]
Optymalne rozwiązanie opisałem już przecież powyżej (co nie znaczy że jest dobre, bo ma dużą złożoność i może da się prościej):

• korzystamy z uogólnionego algorytmu wydawania reszty: każdy zbiór przedstawia nam jeden nominał. Wartość nominału stanowi moc zbioru. Oczywiście dwa zbiory o tej samej mocy, ale róznych elementach zbioru są róznymi zbiorami! Następnie wykonujemy kroki algorytmu wydawania reszty tak jak zawsze, ale musimy robić tutaj rekurencję tak aby rozpatrywać wszystkie możliwości wykorzystania zbiorów o tej samej mocy. Dodatkowo zawsze musimy pamiętać o tym żeby sprawdzać moc połączonego zbioru (aktualnego z tym który rozpatrujemy) a nie sumę mocy obu zbiorów.

Przy czym proponuje mieć na uwadze to że może być znacznie łatwiejsze i sensowniejsze rozwiązanie :P Proponuje pomyśleć nad redukcją tego problemu do jakiegoś innego znanego problemu o podobnych własnościach.

Nie wiem czy dobrze zrozumiałem, a więc dla takiego przykładu zróbmy to:

nr_zbioru : zbiór_wartości
1: {1,2,3}
2: {7,8,11}
3: {1,2,3,4}
4: {1}
5: {8,9}

Dla n=11.

Działania, które zrozumiałem że mam podjąć:
Mam wykonać n-1 razy problem wydawania reszty (Algorytm zachłanny), czyli...

Operuję na zbiorze {1,2,3} o mocy równej 3. Względem zbioru numer 1 wyznaczam moce zbiorów dla pozostałych zbiorów uwzględniając w wyznaczonej mocy zbioru wartości bez duplikatów czyli
{1,2,3} vs {7,8,11} = 3 - moc zbioru numer 2
{1,2,3} vs {1,2,3,4} = 1 - moc zbioru numer 3
{1,2,3} vs {1} = 2 - moc zbioru numer 4
{1,2,3} vs {8,9} = 5 - moc zbioru numer 5

Sortuję malejąco wyniki, czyli mam:
{8,9} = |5|
{7,8,11} = |3|
{1} = |2|
{1,2,3,4} = |1|

I wykonuję algorytm zachłanny:
krok1: {1,2,3} + {8,9} = 5 (5 <= n=11)
krok2: {1,2,3} + {8,9} + {7,8,11} = 5 + 3 = 8 (8 <= n=11)
krok3: {1,2,3} + {8,9} + {7,8,11} + {1} = 8 + 2 = 10 (10 <= n=11 )
krok4: {1,2,3} + {8,9} + {7,8,11} + {1} + {1,2,3,4} = 10+1 (11 <= n=11)

W kroku 4-tym uzyskałem wynik "satysfakcjonujący" dla zbioru {1,2,3}.

W kolejnych krotkach robiłbym to samo ale dla kolejnych zbiorów czyli kolejnym krokiem byłoby działanie na zbiorze liczb {{7,8,11}} porównanie go z resztą zbiorów, a następnie wykonanie algorytmu zachłannego i wtedy jeżeli osiągniemy wartość >= n z wykorzystaniem mniejszej ilości zbiorów to bierzemy ten wynik za optymalny na danym etapie.

Tylko tu mi coś nie gra, bo w ten sposób będziemy musieli wykonać "full service" czyli przetrzepać wszystkie możliwości aby dojść do satysfakcjonującego wyniku, tak ?

Post wyżej napisałeś że jest to opcja na rozwiązanie przybliżone, a teraz że na optymalne, a więc które ? Wygląda że dokładne, w końcu złożoność kosmiczna i wszystkie przypadki rozpatrzone a więc optymalne jest.

Złożoność wykładnicza dla tego rozwiązania, tak ?

1. Wykładnicza, tak, ale tylko w bardzo szczególnym przypadku
2. Rozwiązanie dokładne, ale wydaje mi się że jednak musisz zastosować algorytm dynamiczny wydawania reszty, a nie zachłanny.
3. Wybrałeś sobie optymistyczny przykład bo nie miałeś zbiorów równolicznych dla których musiałbyś prowadzić niejako "równoległe obliczenia"

Shalom napisał(a)

1. Wykładnicza, tak, ale tylko w bardzo szczególnym przypadku
2. Rozwiązanie dokładne, ale wydaje mi się że jednak musisz zastosować algorytm dynamiczny wydawania reszty, a nie zachłanny.
3. Wybrałeś sobie optymistyczny przykład bo nie miałeś zbiorów równolicznych dla których musiałbyś prowadzić niejako "równoległe obliczenia"

ad2) Dynamiczny wydawania reszty to znaczy masz na myśli oparty na programowaniu dynamicznym czyli z optymalną pod-strukturą, tak ?

Czy nadużyję Twojej pomocy jeżeli poproszę jeszcze o jakąkolwiek pomoc w kwestii rozwiązania przybliżonego ?

Dziękuje za poświęcony czas :)