Algorytmika zachłanna, programowanie dynamiczne

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

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.

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

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.

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]);
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.

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/Problem_plecakowy#Rozwiązania_dynamiczne

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/

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

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