PROGRAMOWANIE – PRZYKŁADY
IDE C++ WinBGI C# Wpadki

Przykład C++

Problem plecakowy Strategie pakowania Metoda prób i błędów Implementacja metody w C++ Drzewo przeszukiwań algorytmu Program w C++ Poprzedni przykład Następny przykład Program w Visual C# Kontakt

Problem plecakowy

Zadaniem programu jest rozwiązanie tzw. problemu pleca­kowego (ang. knapsack problem), a dokła­dniej jednej z jego różnych wersji zwanej dyskre­tnym problemem pleca­kowym (ang. 0-1 knapsack problem). Problem polega na wyborze takiego zestawu przedmiotów z danego zbioru przedmiotów o podanej wadze i wartości, aby suma ich wartości była możliwie jak największa i suma ich wag była nie większa od pojemności plecaka.

Zagadnienie można zobrazować na przykładzie Alibaby, który znalazł w Sezamie skarb i ma wynieść z niego część o jak najwyż­szej wartości. Skarb składa się z przed­miotów, z których każdy ma określoną wagę i wartość. Kłopot Alibaby polega na tym, że może odbyć drogę powrotną tylko raz, a plecak, który ma ze sobą, porwie się, jeśli łączna waga zabranych przed­miotów przekroczy pewien dopuszczalny ciężar. Można spotkać inną wersję przedsta­wienia problemu, w której złodziej rabujący sklep jubilera stoi przed dylematem wyboru jak najwarto­ściowszego łupu o ograni­czonym ciężarze całko­witym. W rzeczy­wistych zastoso­waniach problem plecakowy może dotyczyć nie tylko pakowania plecaka, walizki czy paczki, lecz także samochodu, ciężarówki, samolotu, statku itp.

Strategie pakowania

W praktyce podczas pakowania plecaka postępujemy najczęściej według jednej z następu­jących strategii:

Strategie te opierają się na działaniu zachłannym, które może prowadzić do znale­zienia akcepto­walnego rozwią­zania, lecz nieko­niecznie optymal­nego. Przypo­mnijmy (por. program wydawania reszty), że algorytm zachłanny (ang. greedy algorithm) polega na dokony­waniu w każdym kroku wyboru, który wydaje się być w danym momencie najlepszy. Dla każdej z powyż­szych strategii można łatwo podać dane, dla których uzyskane rozwią­zanie nie jest optymalne. Gdyby np. Alibaba wybierał za każdym razem przed­miot o najwyż­szej wartości (pierwsza strategia), to w przy­padku skarbu złożonego z trzech przedmiotów i plecaka o parame­trach:

Przedmiot  Waga  Wartość
    1       25      40
    2       42      68
    3       20      56
Pojemność plecaka:  50

wyniósłby z Sezamu tylko jeden przedmiot o wadze 42 i wartości 68 zamiast dwóch przedmiotów o łącznym ciężarze 45 i wartości 96. Oczywiście w tym szcze­gólnym przypadku podjęcie najlepszej decyzji nie nastręcza żadnych trudności, generalnie jednak problem plecakowy nie jest łatwy do rozwią­zania.

Metodą zapewniającą znalezienie optymalnego rozwiązania problemu pleca­kowego jest tzw. metoda programo­wania dynami­cznego. Jej nazwa nie odnosi się programo­wania rozumia­nego jako proces projekto­wania i tworzenia programów kompute­rowych, chociaż można ją zapisać w postaci programu dla komputera. Istotą metody jest umiejętne wypeł­nianie tabel wyraża­jących rozwią­zania mniejszych problemów odpowia­dających mniejszej liczbie przedmiotów i mniejszej pojemności plecaka oraz ich zwiększanie aż do uzyskania rozwią­zania całkowitego.

W dalszych rozważaniach zajmiemy się poszukiwaniem optymal­nego rozwią­zania problemu pleca­kowego metodą prób i błędów. Algorytmy o tej własności są nazywane algorytmami z powrotami lub z nawrotami. Charakte­ryzują się one tym, że kolejny krok, który może prowadzić do rozwiązania, jest zapisywany, a gdy później okaże się, że nie prowadzi do rozwiązania, następuje usunięcie jego zapisu i wyco­fanie się do stanu poprzedza­jącego błędną decyzję. Najbardziej naturalnym opisem algorytmów z powrotami jest rekurencja.

Metoda prób i błędów

Poszukiwanie optymalnego rozwiązania dyskretnego problemu plecako­wego (0-1 knapsack problem) metodą prób i błędów polega na systema­tycznym podejmo­waniu kolejnych prób dobierania przedmiotów, aż wszystkie dopuszczalne kombi­nacje, w których każdy przedmiot może być pozosta­wiony w Sezamie (0) albo zabrany przez Alibabę (1), zostaną wyczerpane. Jeżeli przedmioty ponume­rujemy kolejnymi liczbami całkowi­tymi od 1 do n, wstępną wersję algorytmu próbującego wykonać kolejny krok dla przedmiotu k możemy sformu­łować następu­jąco:

void probuj(int k)
{
    if (k < n) probuj(k + 1);
    if (można dołożyć przedmiot k do plecaka)
    {
        zapisz, że Alibaba zabiera przedmiot k;
        if (wartość wynoszonej części skarbu jest wyższa)
            zapamiętaj nowy zestaw i jego wartość;
        if (k < n) probuj(k + 1);
        usuń zapis, że Alibaba zabiera przedmiot k;
    }
}

Funkcja zawiera dwa bezpośrednie wywołania rekuren­cyjne samej siebie dotyczące przejścia do nastę­pnego przedmiotu o numerze k+1. Pierwsze przejście odbywa się bez zabie­rania przedmiotu k. Drugie zachodzi wtedy, gdy Alibaba może dołożyć do plecaka przedmiot k. Jeżeli polepsza to wartość wynoszonej części skarbu, nowy zestaw zgroma­dzonych przedmiotów i ich łączna wartość zostaje zapamiętana. Na koniec drugiego wywołania dołożony do zestawu przedmiot k jest z niego usuwany, by w później­szych próbach podejmo­wanych po powrocie do niższych od k argumentów można było uzwględnić zestawy bez przedmiotu k (rys.).

Rzecz jasna poszukiwanie optymalnego rozwiązania problemu plecako­wego należy rozpocząć od wywołania funkcji probuj dla argu­mentu 1 przy pustym zestawie przedmiotów do wynie­sienia. Gdy w trakcie działania funkcji napotkany zostanie bardziej wartościowy zestaw przedmiotów nieprzekra­czający pojemności plecaka, zostaje zapamię­tany zamiast dotychcza­sowego. Ostatni taki zestaw wykryty przed końcem jej wykonania stanowi rozwiązanie optymalne, ponieważ wszystkie dopuszczalne kombi­nacje przedmiotów zostały zanali­zowane.

Implementacja metody w C++

W celu uściślenia przedstawionej powyżej funkcji probuj stanowiącej wstępne sformu­łowanie metody prób i błędów poszuku­jącej optymalnego rozwią­zania problemu plecako­wego w C++ użyjemy następu­jących zmiennych, w których będą przecho­wywane dane oraz wyniki pośrednie i końcowe:

int n;                  // Liczba przedmiotów
double *w = NULL;       // Wagi przedmiotów
double *p = NULL;       // Wartości przedmiotów
double cMax;            // Dopuszczalna pojemność plecaka

double c;               // Ciężar bieżącego zestawu
double v;               // Wartość bieżącego zestawu
bool *s = NULL;         // Skład bieżącego zestawu
double cOpt;            // Ciężar optymalnego zestawu
double vOpt;            // Wartość optymalnego zestawu
bool *sOpt = NULL;      // Skład optymalnego zestawu

Cztery zmienne typu wskaźnikowego reprezentują tablice dynamiczne. Chociaż ich elementy są indeksowane od zera wzwyż, nic nie stoi na przeszko­dzie, aby na razie pozostać przy używaniu indeksów zgodnych z numerami przedmiotów od 1 do n. Pierwsza grupa czterech zmiennych określa parametry skarbu (liczbę przedmiotów, ich wagi i wartości) oraz pojemność plecaka, pozostałe specy­fikują aktualnie rozpatry­wany i najlepszy napotkany zestaw przedmiotów (bieżący i poten­cjalnie optymalny). Skład zestawów precyzują tablice o elementach typu bool przyjmu­jących wartość true, gdy przedmiot wchodzi w skład zestawu, lub false, gdy jest w nim pominięty. Gdy rozpatry­wany w kolejnej próbie zestaw bieżący jest lepszy od dotychczas najle­pszego, zostaje zapamię­tany jako najlepszy:

void zanotuj()
{
    cOpt = c;
    vOpt = v;
    for (int k = 1; k <= n; k++)
        sOpt[k] = s[k];
}

Uściślony algorytm podejmowania próby dla przedmiotu k możemy teraz zapisać następu­jąco:

void probuj(int k)
{
    if (k < n) probuj(k + 1);
    c += w[k];
    if (c <= cMax)
    {
        v += p[k];
        s[k] = true;
        if (v > vOpt) zanotuj();
        if (k < n) probuj(k + 1);
        s[k] = false;
        v -= p[k];
    }
    c -= w[k];
}

Na początku, gdy liczba wszystkich przedmiotów, ich wagi i wartości oraz dopuszczalna pojemność plecaka jest znana, trzeba zainicja­lizować zmienne opisujące zestaw bieżący i optymalny przyjmując, że obydwa zestawy są puste, po czym rozpocząć poszuki­wanie rozwiązania problemu metodą prób i błędów od przedmiotu o numerze 1:

c = v = 0;
for (int k = 1; k <= n; k++)
    s[k] = false;
zanotuj();
probuj(1);

Drzewo przeszukiwań algorytmu

Działanie algorytmu z powrotami można prześledzić na przyto­czonym powyżej przykła­dzie problemu pleca­kowego dla trzech przedmiotów o wagach 25, 42 i 20, warto­ściach 40, 68 i 56 oraz pojemności plecaka wynoszącej 50 jednostek. Prosta analiza prowadzi do przedsta­wionego na poniższym rysunku binarnego drzewa przeszu­kiwań.

W wierzchołkach drzewa są wpisane numery przedmiotów występujące w roli argumentów kolejnych wywołań funkcji probuj. Czerwona linia zakończona strzałką wskazuje kierunek wędrówki po wierzchołkach wzdłuż krawędzi drzewa. Lewe krawędzie odpowia­dają przejściu do nastę­pnego przedmiotu bez zabie­rania przedmiotu określonego w wierz­chołku, a prawe – przejściu po zabraniu go. Obcięcie ostatniej krawędzi oznacza, że wędrówka wzdłuż niej nie ma sensu ze względu na przekro­czenie dopuszczalnej pojemności plecaka. Etykiety pod wierzchołkami opisują rozpatry­wany bieżący zestaw przedmiotów (łączny ciężar, wartość i skład). Gwiazdka oznacza, że jest on dotąd najlepszy i jako taki zostaje zapamiętany poprzez wywołanie funkcji zanotuj. Ostatnia na drodze gwiazdka określa rozwiązanie optymalne.

Dla większej liczby przedmiotów drzewo przeszukiwań może być bardzo rozbudo­wane, co może wpłynąć negaty­wnie na złożoność czasową algorytmu. Nie oznacza to jednak, że zawsze tak jest. Często podczas kolejnych prób binarne drzewo przeszukiwań jest stopniowo obcinane ze względu na przekro­czenie pojemności plecaka, przez co ich liczba redukuje się i algorytm daje się wykonać w rozsądnym czasie.

Program w C++

Pełny program konsolowy w języku C++ znajdujący optymalne rozwiązanie dyskre­tnego problemu pleca­kowego metodą prób i błędów jest przedsta­wiony na poniższym listingu. W programie uwzglę­dniono naturalną w C++ indeksację elementów tablic od zera wzwyż i przyjęto zgodną z indeksami wewnętrzną numerację przedmiotów od 0 do n-1, co wymagało niewielkiej modyfi­kacji omówionych wyżej funkcji probujzanotuj oraz kodu inicju­jącego wyszuki­wanie rozwią­zania.

#include <iostream>
#include <iomanip>
#include <fstream>
#include <string>

using namespace std;

int n;                  // Liczba przedmiotów
double *w = NULL;       // Wagi przedmiotów
double *p = NULL;       // Wartości przedmiotów
double cMax;            // Dopuszczalna pojemność plecaka

double c;               // Ciężar bieżącego zestawu
double v;               // Wartość bieżącego zestawu
bool *s = NULL;         // Skład bieżącego zestawu
double cOpt;            // Ciężar optymalnego zestawu
double vOpt;            // Wartość optymalnego zestawu
bool *sOpt = NULL;      // Skład optymalnego zestawu

void error(string err)
{
    if (sOpt != NULL) delete[] sOpt;
    if (s != NULL) delete[] s;
    if (p != NULL) delete[] p;
    if (w != NULL) delete[] w;
    cout << err << endl;
    getchar();
}

void naglowek()
{
    cout << "---------------------------\n";
    cout << "Przedmiot Waga Wartość\n";
    cout << "---------------------------\n";
    cout.setf(ios::fixed, ios::floatfield);
    cout.setf(ios::showpoint);
    cout.precision(2);
}

bool dane()
{
    cout << "Nazwa pliku: ";
    string nazwa;
    cin >> nazwa;
    ifstream plik(nazwa.c_str());
    if (!plik)     {
        error("Nieudane otwarcie pliku.");
        return false;
    }
    if (!(plik >> n) || !(n > 0))
    {
        error("Oczekiwana liczba całkowita dodatnia.");
        return false;
    }
    naglowek();
    w = new double[n];
    p = new double[n];
    s = new bool[n];
    sOpt = new bool[n];
    for (int k = 0; k < n; k++)
    {
        if (!(plik >> w[k] >> p[k]) || !(w[k] > 0 && p[k] > 0))
        {
            error("Oczekiwana liczba rzeczywista dodatnia.");
            return false;
        }
        cout << setw(5) << k + 1 << setw(11) << w[k] << setw(11) << p[k] << endl;
    }
    if (!(plik >> cMax) || !(cMax > 0))
    {
        error("Niewłaściwa pojemność plecaka.");
        return false;
    }
    cout << "---------------------------\n";
    cout << "Pojemność plecaka:" << setw(9) << cMax << endl;
    return true;
}

void zanotuj()
{
    cOpt = c;
    vOpt = v;
    for (int k = 0; k < n; k++)
        sOpt[k] = s[k];
}

void probuj(int k)
{
    if (k < n - 1) probuj(k + 1);
    c += w[k];
    if (c <= cMax)
    {
        v += p[k];
        s[k] = true;
        if (v > vOpt) zanotuj();
        if (k < n - 1) probuj(k + 1);
        s[k] = false;
        v -= p[k];
    }
    c -= w[k];
}

void wynik()
{
    cout << "\nZestaw optymalny\n";
    naglowek();
    for (int k = 0; k < n; k++)
        if (sOpt[k])
            cout << setw(5) << k + 1 << setw(11) << w[k] << setw(11) << p[k] << endl;
    cout << "---------------------------\n";
    cout << "Optimum:" << setw(8) << cOpt << setw(11) << vOpt << endl;
}

int main()
{
    if (dane())
    {
        c = v = 0;
        for (int k = 0; k < n; k++)
            s[k] = false;
        zanotuj();
        probuj(0);
        wynik();
        delete[] sOpt;
        delete[] s;
        delete[] p;
        delete[] w;
        return 0;
    }
    else
        return 1;
}

Program rozpoczyna działanie od wczytania danych z pliku teksto­wego o nazwie podanej z klawia­tury. Przyjęto, że w pierwszym wierszu pliku podana jest liczba przedmiotów, w następnych wierszach po dwie liczby określa­jące wagę i wartość kolejnego przedmiotu, a w ostatnim wierszu pojemność plecaka. Na poniższym rysunku przedsta­wiony jest wynik wykonania programu dla przykła­dowych danych zawartych w pliku Dane1.txt.


Opracowanie przykładu: styczeń 2020