Algorytmika zachłanna, programowanie dynamiczne

Odpowiedz Nowy wątek
2018-11-06 08:55
0

Mamy n przedmiotów, z których każdy ma pewną całkowitą masę. Zaproponuj algorytm, który
wyznaczy całkowite wypełnienie przyczepy (o ładowności M będącej liczbą całkowitą) używając
do tego jak najmniej przedmiotów (lub stwierdzi, że całkowite wypełnienie nie jest możliwe):

dla M=10 i n=6 przedmiotów o masach 5, 7, 4, 4, 2, 5 wystarczą 2 przedmioty (o masach 5 i 5)

pomoże ktoś z tym algorytmem?
Jak go zaimplementować? Najlepiej w pseudokodzie

@spamgolden: mógłbyś zatytułować wątek w sposób opisujący problem? - somekind 2018-11-06 11:41

Pozostało 580 znaków

2018-11-06 09:16
1

Najprostsza heurystyka zachłanna - posortować przedmioty wg malejącej masy. Następnie dobierasz przedmioty z listy po kolei aż nie zapełnisz przyczepy. Oczywiście może się okazać na końcu, że zostało wolne miejsce, ale nie mieści się żaden przedmiot. Wtedy bierzesz najmniejszy pozostały przedmiot, umieszczasz go w przyczepie, montujesz solidnie taśmą aby nie wypadł i jeśli za bardzo wystaje, przywiązujesz taką czerwoną szmatkę na końcu.

Pozostało 580 znaków

2018-11-06 09:17
0

Jest to typowy problem wydawania reszty:
Problem wydawania reszty

na Wikipedii są opisane oba algorytmy zarówno zachłanny jak i dynamiczny, w Twoim wypadku jedynie dynamiczny będzie poprawnym rozwiązaniem


It's easy to hate code you didn't write, without an understanding of the context in which it was written.

Pozostało 580 znaków

2018-11-06 09:28
0

Niezupełnie typowy, bo w algorytmie wydawania reszty monety mogą się powtarzać. Natomiast tu z treści zadania wynika, że raczej nie mogą, chyba że jakoś to źle zrozumiałem. Brak dopuszczalności powtórzeń powoduje, że problem jest trudniejszy, i szczerze przy tym założeniu nie widzę tu programowania dynamicznego.

edytowany 1x, ostatnio: Krolik, 2018-11-06 09:28
Kolega OP podał przykład " 5, 7, 4, 4, 2, 5 " i tu 4 się powtarza. - yarel 2018-11-06 09:29
Nie, nie powtarza się. Każda czwórka jest użyta co najwyżej raz. - Krolik 2018-11-06 09:42
Żeby było z powtórzeniami, to musiałbyś mieć brak ograniczenia na liczbę powtórzeń. Jeśli masz jakiekolwiek skończone ograniczenie na maksymalną liczbę powtórzeń danego elementu, to nie jest to standardowy problem wydawania reszty i standardowe rozwiązanie z programowaniem dynamicznym nie będzie działać. - Krolik 2018-11-06 09:43
mi się wydaję że wystarczy tyko zmodyfikować klasyczne rozwiązanie dynamiczne, potrzebujemy dodatkowej tablicy m x n do zapisania informacji ile razy skorzystaliśmy z danego nominału do obliczenia danej kwoty, a dalej już w klasycznym rozwiązaniu po prostu sprawdzać czy nie przekroczyliśmy limitu użycia danego nominału - neves 2018-11-06 09:44
Muszę dopić kawę i przeczytać jeszcze raz :D Wydawało mi się, że dla autora 5+5 jest dobrym rozwiązaniem (pomijając algorytm, który to wyliczy), a Tobie chodzi o konkretny algorytm, w którym elementu używamy co najwyżej raz, tak? - yarel 2018-11-06 09:49
Nie mogą się powtarzać. Zauważcie że są 2 elementy o masie 5. Więc wydawanie reszty odpada. Macie jakieś pomysły? - spamgolden 2018-11-06 10:19

Pozostało 580 znaków

2018-11-06 10:30
0

Jak dla mnie algorytm dynamiczny do wydawanie reszty, ze śledzeniem ile razy użyliśmy danego przedmiotu jak najbardziej da radę:

Edytka: pozbyłem się dodatkowej tablicy i teraz kod wygląda bardziej czytelnie:

int n = 4;
int M = 10;
int[] masaPrzedmiotu     = new int[] { 2, 4, 5, 7 };
int[] licznoscPrzedmiotu = new int[] { 1, 2, 2, 1 }; 
int[,] minLiczbaPrzedmiotow = new int[n, M + 1]; 

for (int j = 1; j <= M; ++j) minLiczbaPrzedmiotow[0, j] = int.MaxValue;

// pierwszy przedmiot
for (int k = 0; k <= licznoscPrzedmiotu[0]; ++k)
{
    int waga = k * masaPrzedmiotu[0];
    if (waga <= M)
    {
        minLiczbaPrzedmiotow[0, waga] = k;
    }
}

// kolejne przedmiot
for (int i = 1; i < n; ++i)                                  // iterujemy po przedmiotach/nominałach
{
    for (int j = 1; j <= M; ++j)                             // iterujemy po masie/kwocie 
    {
        minLiczbaPrzedmiotow[i, j] = int.MaxValue;                    

        for (int k = 0; k <= licznoscPrzedmiotu[i]; ++k)     // iterujemy po liczbie dostępnych egzemplarzy przedmiotu
        {                        
            int masaCalkowitaBezMasyObecnego = j - k * masaPrzedmiotu[i];

            if ((masaCalkowitaBezMasyObecnego > -1) && (minLiczbaPrzedmiotow[i - 1, masaCalkowitaBezMasyObecnego] != int.MaxValue)) 
            {
                int liczbaPrzedmiotowGdyWezmiemyKObecnego = minLiczbaPrzedmiotow[i - 1, masaCalkowitaBezMasyObecnego] + k;

                if (liczbaPrzedmiotowGdyWezmiemyKObecnego < minLiczbaPrzedmiotow[i, j])
                    minLiczbaPrzedmiotow[i, j] = liczbaPrzedmiotowGdyWezmiemyKObecnego;
            }
        }

    }
}

Console.WriteLine(minLiczbaPrzedmiotow[n-1, M]);

It's easy to hate code you didn't write, without an understanding of the context in which it was written.
edytowany 7x, ostatnio: neves, 2018-11-06 13:56

Pozostało 580 znaków

2018-11-06 11:17
0

mi się wydaję że wystarczy tyko zmodyfikować klasyczne rozwiązanie dynamiczne, potrzebujemy dodatkowej tablicy m x n do zapisania informacji ile razy skorzystaliśmy z danego nominału do obliczenia danej kwoty, a dalej już w klasycznym rozwiązaniu po prostu sprawdzać czy nie przekroczyliśmy limitu użycia danego nominału

Nie analizowałem dokładnie Twojego algorytmu, ale jeśli to jest jedyna modyfikacja względem algorytmu wydawania reszty, to nie będzie działać.
Tzn. będzie działać, ale nie będzie gwarantować optymalnych rozwiązań, ponieważ zadanie nie jest wtedy prawidłowo podzielone na etapy. Ba, może w ogóle nie znaleźć rozwiązania, mimo że istnieje.

Nie masz spełnionego warunku niezależności etapów, tzn. przyszłe stany są u Ciebie zależne od poprzednich, a to jest warunek konieczny dla działania programowania dynamicznego.

Przykładowo dla przedmiotów:

{3, 4, 4, 5} i pojemności 11 prawidłowym rozwiązaniem jest { 4, 4, 3 }.
Jednak dla etapu n = 8 wynik możesz skonstruować na 2 równoważne sposoby { 4, 4 } oraz { 5, 3 }. W klasycznym algorytmie wydawania reszty nie ma znaczenia, który ze sposobów wybierzesz, więc etap dla n= 8 jest całkowicie niezależny od kolejnych etapów i dlatego programowanie dynamiczne działa - właśnie poprzez redukcję tych wszystkich równoważnych przypadków do jednego. W klasycznym algorytmie wydawania reszty trójkę możesz powtórzyć, więc ostatecznie miałbyś 2 równoważne rozwiązania { 5, 3, 3 } oraz { 4, 4, 3 }. Jednak tutaj, jeśli wybierzesz { 5, 3 } to zabraknie Ci potrzebnego elementu w etapie dla n = 11 i algorytm zakończy się ze stwierdzeniem, że nie znaleziono rozwiązania, bo nie masz już drugiej trójki.

edytowany 5x, ostatnio: Krolik, 2018-11-06 11:23
ale podział na etapy zostaje dokładnie ten sam, i daje dobry wynik dla podanego przykładu ;) - neves 2018-11-06 11:55
Nie o faktycznie, chyba masz rację, nie zwróciłem uwagi, że nominały są w zewnętrznej pętli. Dzięki za poprawienie kodu aby był czytelniejszy. - Krolik 2018-11-06 15:59

Pozostało 580 znaków

2018-11-06 15:06
1

A to nie jest po prostu problem plecakowy dyskretny, z tą różnicą że "wartość" przedmiotów jest ujemna bo chcemy ich zabrać jak najmniej?
https://pl.wikipedia.org/wiki[...]cakowy#Rozwiązania_dynamiczne


Masz problem? Pisz na forum, nie do mnie. Nie masz problemów? Kup komputer...
edytowany 1x, ostatnio: Shalom, 2018-11-06 15:32
Chyba rozchodzi się o różnicę między <=, a =. - yarel 2018-11-06 15:36

Pozostało 580 znaków

2018-11-06 16:21
0

To zdecydowanie jest jakiś przypadek problemu plecakowego. Wygląda na problem sumy podzbioru https://en.wikipedia.org/wiki/Subset_sum_problem z dodatkowym ograniczeniem minimalnej (maksymalnej) ilości elementów.

Minimalną ilość elementów można zamienić na problem maksymalnej ilości elementów. Jeżeli T to zadana pojemność/suma, S to suma wszystkich elementów, to łatwo zauważyć, że problem minimalnej ilość elementów sumujących się do T jest dualny z problemem maksymalnej ilości elementów sumujących się to S-T.

Szybkie wyszukiwanie zwraca przykładowy algorytm (nie weryfikowałem jego poprawności):
https://www.geeksforgeeks.org/maximum-size-subset-given-sum/

edytowany 1x, ostatnio: nalik, 2018-11-06 16:50

Pozostało 580 znaków

2018-11-06 18:18
1

Po przeczytaniu https://www.geeksforgeeks.org/subset-sum-problem-dp-25/, jeszcze bardziej uprościłem kod pozbywając się jednej z pętli:

int n = 6;
int M = 11;
int[] masaPrzedmiotu = new int[] { 5, 7, 4, 4, 2 ,5 };

int[,] minLiczbaPrzedmiotow = new int[n, M + 1];

for (int j = 1; j <= M; ++j) minLiczbaPrzedmiotow[0, j] = int.MaxValue;            

if (masaPrzedmiotu[0] <= M)
{
    minLiczbaPrzedmiotow[0, masaPrzedmiotu[0]] = 1;
}            

// kolejne przedmiot
for (int i = 1; i < n; ++i)                                  // iterujemy po przedmiotach/nominałach
{
    for (int j = 1; j <= M; ++j)                             // iterujemy po masie/kwocie 
    {
        minLiczbaPrzedmiotow[i, j] = minLiczbaPrzedmiotow[i - 1, j];

        int masaCalkowitaBezMasyObecnego = j -  masaPrzedmiotu[i];

        if ((masaCalkowitaBezMasyObecnego > -1) && (minLiczbaPrzedmiotow[i - 1, masaCalkowitaBezMasyObecnego] != int.MaxValue))
        {
            int liczbaPrzedmiotowGdyWezmiemyObecnego = minLiczbaPrzedmiotow[i - 1, masaCalkowitaBezMasyObecnego] + 1;

            minLiczbaPrzedmiotow[i, j] = Math.Min(liczbaPrzedmiotowGdyWezmiemyObecnego, minLiczbaPrzedmiotow[i, j]);
        }
    }
}

Console.WriteLine(minLiczbaPrzedmiotow[n - 1, M]);

It's easy to hate code you didn't write, without an understanding of the context in which it was written.
edytowany 1x, ostatnio: neves, 2018-11-06 18:21

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0