Problem jest następujący: mam zbiór liczb całkowitych nieujemnych i zadaną "sumę" - liczbę jw. Potrzebuję wyznaczyć, czy z tego zbioru da się wyznaczyć podzbiór, który po zsumowaniu da poszukiwaną "sumę". Ze względu na rozmiar danych algorytm "naiwny" O(n!) nie wchodzi w grę. Czy ma ktoś jakieś pomysły?
Z góry dziękuję i pozdrawiam.
Pomyśl jak bankier: masz jakąś kwotkę i chcesz ją podzielić na jak najmniej banknotów. Największy banknot jaki posiadasz to 1000.
Obliczasz ile banknotów 1000 zmieści się w w posiadanej sumie, czyli jest to pierwsa poszukiwana wartość. Odejmujesz sumę tysiączek od posiadanej wartości i zaczynasz od nowa dla kolejnego banknotu o niższej wartości, tutaj 500.
Wracając do zadania: posortuj malejąco zbiór liczb i zacznij od największej z nich, czyli pierwszej.
int main()
{
int x;
srand(GetTickCount);
int suma = abs(rand());
printf("suma: %d\n", suma);
int wartosc[] = {1000,500,200,100,50,20,10,5,2,1};
int ilosc[] = {0,0,0,0,0,0,0,0,0,0};
#define items (sizeof(wartosc)/sizeof(wartosc[0]))
for (x=0; x<items; x++)
{
ilosc[x] = suma/wartosc[x];
suma -= (wartosc[x] * ilosc[x]);
if (ilosc[x]) printf("%d * %d\n", ilosc[x], wartosc[x]);
}
Ok, ale co jeżeli liczby mamy takie: (49, 47, 45, 42, 7, 6, 2), a suma ma wynosić 50. Wtedy zaczynając od 49 zostaje 1 i nie da rady dalej. Można więc przeskoczyć, zaczynać od kolejnej (47) i dalej, aż w końcu zaczynając od 42 musimy znowu przeskoczyć 7 bo wtedy zostanie 1 i dopiero mamy podzbiór (42, 6, 2).
W związku z tym mamy pesymistyczną złożoność O(n!) i właśnie ten algorytm miałem na myśli za niestosowalny.
Chyba że nie zrozumiałem :-)
programowanie dynamiczne powinno rozwiązać problem. looknij dyskretny problem plecakowy (0-1 knapsack problem)
o(n!) to przesada, "siłowe" rozwiązanie to 2^N
Tak, ja mam pomysł: weź kartkę i siądź nad zadaniem sam a nie szukaj rozwiązania na forum.
To praca samodzielna, nie zbiorowa!
Dla niewtajemniczonych:
Kolega na 100% bierze udział w Potyczkach Algorytmicznych 2007 i nie wie jak zrobić zadanie ko2.
maxbog napisał(a)
Tak, ja mam pomysł: weź kartkę i siądź nad zadaniem sam a nie szukaj rozwiązania na forum.
To praca samodzielna, nie zbiorowa!Dla niewtajemniczonych:
Kolega na 100% bierze udział w Potyczkach Algorytmicznych 2007 i nie wie jak zrobić zadanie ko2.
To może ja też wystartuję :D
ostatnio miałem na algebrze równania diofantyczne, czy tego się nie da tu zastosować?
na PA był troche inny problem - chyba że kolega miał na myśli multizbiór :]
http://www.oi.edu.pl/php/show.php?ac=p180702&module=show&file=zadania/oi12/ban1
i uważam że należy odpowiadać ludziom na takie pytania nawet w trakcie zawodów, to że jeden widział to zadanie, a drugi nie, ma decydować który jest lepszy? umie sformułować podproblem jako zadanie standardowe/klasyczne i to jest najważniejsze.