axelbest
27-02-2012 10:57:14
Witam, mam pewne zadanie do wykonania i nie wiem jakiego algorytmu użyć. Problem polega na tym że mam kilka tzw próbek: wyznaczają one ilość elementów jakie mogę otrzymać w jednej akcji danej maszyny. Np el_1=2,el_2=1. Oznacza to ze w jednej akcji maszyny otrzymamy 2 elementy pierwszego typu i jeden element typu drugiego. Maszyna tworzy 10 elementow - tak wiec można to opisać jako el_1=2,el_2=1,el_4=0,el_5=0 ...el_10=0;
Zadanie polega na tym ze mam macierz takich próbek (zminimalizuje ją na potrzeby posta do 3)
probka1. el_1=2,el_2=1;
probka2. el_2=2,el_3=1;
probka3. el_1=1,el_3=2;
Mając takie dane potrzebne jest określenie najbardziej optymalnego rozwiązania dla wymaganych elementow el_1,el_2,el_3. Na wejsciu otrzymuje listę elementów które są wymagane (poniżej 2 przypadki)
1 przypadek = Potrzebnych jest 10 elementów nr1 i 6 elementów nr 2;
Najkorzystniejszą opcją ma być tutaj wybranie probki nr 1 6 razy - dzieki temu otrzymamy 6 elementow nr 2 oraz 12 elementow nr 1. Tak więc jak widać nie jest to chyba problem plecakowy - bo tam mamy założenie że istnieje maksimum.
Drugi przypadek jest gorszy
Na przykład potrzebujemy 5 elementów nr 1, 6 nr2 i 7 nr 3.
Czyli wiadome jest ze probka nr3 bedzie wykonana 4 razy - co da nam juz 4 elementy nr 1, potem wychodzi ze potrzebujemy jednej probki nr 1 co da nam juz piąty element nr1 oraz jeden element nr 2. Brakuje nam teraz 5 elementów nr2 - czyli mozemy wykonanc probke nr 2 3 razy i miec nadmiar jednego elementu nr 2 oraz 3 nadmiarowe elementy nr 4.
Łącznie wychodzi że przy takim wybieraniu probek - mamy nadmiar, ale czy jest on optymalny ? żaden element nie ma konkretnej wagi która by mogła pomóc w takim algorytmie. Głównym celem algorytmu jest otrzymanie jak najmniejszej ilości nadmiarowych elementów.
Moje pytanie brzmi - czy tego typu problem istniał już i czy istnieje algorytm ? Proszę o ukierunkowanie mnie.