Implementacja rozwiązań różnych wariantów problemu plecakowego w języku Python

def sortuj(wartoscDoWagi, indeksy, n):
    for i in range(n - 1):
        for j in range(n - i - 1):
            if wartoscDoWagi[j] < wartoscDoWagi[j + 1]:
                wartoscDoWagi[j], wartoscDoWagi[j + 1] = wartoscDoWagi[j + 1], wartoscDoWagi[j]
                indeksy[j], indeksy[j + 1] = indeksy[j + 1], indeksy[j]

Ogólny problem plecakowy

Specyfikacja problemu:

Dane:

• nazwy – tablica liczb łańcuchów znaków; nazwy poszczególnych przedmiotów

• wartosci – tablica liczb naturalnych; wartości poszczególnych przedmiotów

• wagi – tablica liczb naturalnych; wagi poszczególnych przedmiotów

• n – liczba naturalna; liczba rodzajów przedmiotów

• pojemnosc – liczba naturalna; maksymalna pojemność plecaka

Wynik:

• liczby sztuk poszczególnych przedmiotów (również równe 0), których całkowita waga nie przekracza wartości przechowywanej w zmiennej pojemnosc, a których całkowita wartość jest największa wśród możliwych wypełnień plecaka rzeczami o takiej wadze, która nie przekracza wartości zmiennej pojemnosc

• całkowita wartość spakowanego plecaka

Zaprezentowane rozwiązania będziemy testować dla następujących danych:

• maksymalna pojemność plecaka wynosi 41;

• do dyspozycji mamy nieograniczoną liczbę sztuk każdego rodzaju przedmiotów;

• przedmioty mają następujące wartości oraz wagi:

W programie wykorzystamy dwie funkcje:

• ogolnyPlecak – funkcja mająca na celu znalezienie największej łącznej wartości przedmiotów, które można zmieścić w plecaku o określonej pojemności z wykorzystaniem podejścia zachłannego;

• sortuj – funkcja pomocnicza.

Jak wspomnieliśmy, nie będziemy omawiać funkcji sortuj. Przejdziemy zatem do zapisania funkcji właściwej.

Zapisujemy jej nagłówek. Funkcja przyjmie pięć argumentów:

• nazwy – tablica łańcuchów znaków; nazwy poszczególnych przedmiotów,

• wartosci – tablica liczb naturalnych; wartości poszczególnych przedmiotów,

• wagi – tablica liczb naturalnych; wagi poszczególnych przedmiotów,

• n – liczba naturalna; liczba rodzajów przedmiotów,

• pojemnosc – liczba naturalna; maksymalna pojemność plecaka.

def ogolnyPlecak(nazwy, wartosci, wagi, n, pojemnosc):

W pierwszym kroku tworzone są dwie kolejne tablice:

• wartoscDoWagi – tablica liczb rzeczywistych,

• indeksy – tablica liczb naturalnych.

Obie tablice składają się z n elementów. Zapisujemy pętlę for, która będzie iterować po kolejnych elementach tablic, by je zapełnić.

Każdy i-ty element tablicy wartosci dzielimy przez i-ty element tablicy wagi. Pamiętajmy o wykonaniu rzutowania, by uzyskany wynik był liczbą zmiennoprzecinkową.

Wynik dodajemy do tablicy wartoscDoWagi. Następnie do tablicy indeksy dodajemy kolejne wartości licznika, czyli zmiennej i.

def ogolnyPlecak(nazwy, wartosci, wagi, n, pojemnosc):
    wartoscDoWagi = []
    indeksy = []
    for i in range(n):
        wartoscDoWagi.append(float(wartosci[i]) / wagi[i])
        indeksy.append(i)

Po wyjściu z pętli wywołujemy funkcję sortuj.

Funkcja sortuj przyjmuje trzy argumenty:

• wartoscDoWagi – tablica liczb rzeczywistych,

• indeksy – tablica liczb naturalnych,

• n – liczba naturalna.

def ogolnyPlecak(nazwy, wartosci, wagi, n, pojemnosc):
    wartoscDoWagi = []
    indeksy = []
    for i in range(n):
        wartoscDoWagi.append(wartosci[i] / wagi[i])
        indeksy.append(i)

    sortuj(wartoscDoWagi, indeksy, n)

Po wykonaniu sortowania tworzymy zmienną wynik i przypisujemy jej wartość 0. Zmienna ta będzie przechowywała sumę wartości wybranych przedmiotów.

Tworzymy również tablicę spakowane. Będzie przechowywała liczniki spakowanych przedmiotów.

W kolejnym kroku zapisujemy pętlę for, która będzie iterowała przez posortowane przedmioty. Wykorzystamy ją do wypełnienia tablicy spakowane zerami.

Zapisujemy kolejną pętlę for. Ponownie iterujemy przez posortowane przedmioty.

W pętli utworzymy zmienną indeks, której z każdą iteracją będziemy przypisywać wartość i-tego elementu tablicy indeksy – pobieramy w ten sposób indeks bieżącego przedmiotu.

Zapisujemy pętlę while. Będzie ona wykonywała się tak długo, jak długo waga pakowanego przedmiotu będzie albo mniejsza od pojemności, albo jej równa. Dzięki tej pętli kolejne przedmioty będą mogły być dodawane więcej niż jeden raz.

def ogolnyPlecak(nazwy, wartosci, wagi, n, pojemnosc):
    wartoscDoWagi = []
    indeksy = []
    for i in range(n):
        wartoscDoWagi.append(wartosci[i] / wagi[i])
        indeksy.append(i)

    sortuj(wartoscDoWagi, indeksy, n)
          
    wynik = 0
    spakowane = []
    for i in range(n):
        spakowane.append(0)

    for i in range(n):
        indeks = indeksy[i]
        while wagi[indeks] <= paojemnosc:

Jeśli przedmiot o danym indeksie zmieści się w plecaku, waga przedmiotu odejmowana jest od dostępnej pojemności plecaka (element tablicy wagi o indeksie indeks jest odejmowany od wartości zmiennej pojemnosc). Równocześnie dodajemy wartość tego przedmiotu do wyniku (element tablicy wartosci o indeksie indeks jest dodawany do wartości zmiennej wynik). Inkrementujemy wartość elementu tablicy spakowane o indeksie indeks.

def ogolnyPlecak(nazwy, wartosci, wagi, n, pojemnosc):
    wartoscDoWagi = []
    indeksy = []
    for i in range(n):
        wartoscDoWagi.append(wartosci[i] / wagi[i])
        indeksy.append(i)

    sortuj(wartoscDoWagi, indeksy, n)
          
    wynik = 0
    spakowane = []
    for i in range(n):
        spakowane.append(0)

    for i in range(n):
        indeks = indeksy[i]
        while wagi[indeks] <= pojemnosc:
            pojemnosc -= wagi[indeks]
            wynik += wartosci[indeks]
            spakowane[indeks]++

Po wyjściu z pętli for zapisujemy kolejną pętlę for. Wykorzystamy ją do wypisywania informacji na temat tego, ile sztuk danego rodzaju przedmiotu zostało spakowanych.

Wypisujemy całkowitą wartość spakowanych przedmiotów.

def ogolnyPlecak(nazwy, wartosci, wagi, n, pojemnosc):
    wartoscDoWagi = []
    indeksy = []
    for i in range(n):
        wartoscDoWagi.append(wartosci[i] / wagi[i])
        indeksy.append(i)

    sortuj(wartoscDoWagi, indeksy, n)
          
    wynik = 0
    spakowane = []
    for i in range(n):
        spakowane.append(0)

    for i in range(n):
        indeks = indeksy[i]
        while wagi[indeks] <= pojemnosc:
            pojemnosc -= wagi[indeks]
            wynik += wartosci[indeks]
            spakowane[indeks]++

    for i in range(n):
		print("Liczba spakowanych sztuk przedmiotu " + nazwy[i] + " (indeks " + str(i) + "): " + str(spakowane[i]))
    
    print("\nWartosc spakowanych przedmiotow: ", wynik

Dodajemy wywołanie funkcji.

Pamiętamy również o dodaniu funkcji sortuj.

Oto kompletny kod programu:

def sortuj(wartoscDoWagi, indeksy, n):
    for i in range(n - 1):
        for j in range(n - i - 1):
            if wartoscDoWagi[j] < wartoscDoWagi[j + 1]:
                wartoscDoWagi[j], wartoscDoWagi[j + 1] = wartoscDoWagi[j + 1], wartoscDoWagi[j]
                indeksy[j], indeksy[j + 1] = indeksy[j + 1], indeksy[j]

def ogolnyPlecak(nazwy, wartosci, wagi, n , pojemnosc):
    wartoscDoWagi = []
    indeksy = []
    for i in range(n):
        wartoscDoWagi.append(wartosci[i] / wagi[i])
        indeksy.append(i)

    sortuj(wartoscDoWagi, indeksy, n)
          
    wynik = 0
    spakowane = []
    for i in range(n):
        spakowane.append(0)

    for i in range(n):
        indeks = indeksy[i]
        while wagi[indeks] <= pojemnosc:
            pojemnosc -= wagi[indeks]
            wynik += wartosci[indeks]
            spakowane[indeks] += 1

    for i in range(n):
        print("Liczba spakowanych sztuk przedmiotu " + nazwy[i] + " (indeks " + str(i) + "): " + str(spakowane[i]))

    print("\nWartosc spakowanych przedmiotow:", wynik)

nazwy = ["anemon", "bławatek", "chaber", "dziurawiec", "eustoma", "forsycja", "gipsówka"]
wartosci = [21, 15, 4, 4, 14, 1, 3]
wagi = [11, 8, 5, 4, 7, 1, 7]
n = 7
pojemnosc = 41
ogolnyPlecak(nazwy, wartosci, wagi, n, pojemnosc)

Wynik działania programu:

Liczba spakowanych sztuk przedmiotu anemon (indeks 0): 0
Liczba spakowanych sztuk przedmiotu bławatek (indeks 1): 0
Liczba spakowanych sztuk przedmiotu chaber (indeks 2): 0
Liczba spakowanych sztuk przedmiotu dziurawiec (indeks 3): 1
Liczba spakowanych sztuk przedmiotu eustoma (indeks 4): 5
Liczba spakowanych sztuk przedmiotu forsycja (indeks 5): 2
Liczba spakowanych sztuk przedmiotu gipsówka (indeks 6): 0

Wartosc spakowanych przedmiotow: 76

Decyzyjny problem plecakowy

Specyfikacja problemu:

Dane:

• nazwy – tablica liczb łańcuchów znaków; nazwy poszczególnych przedmiotów

• wartosci – tablica liczb naturalnych; wartości poszczególnych przedmiotów

• wagi – tablica liczb naturalnych; wagi poszczególnych przedmiotów

• n – liczba naturalna; liczba rodzajów przedmiotów

• pojemnosc – liczba naturalna; maksymalna pojemność plecaka

Wynik:

• spakowane przedmioty, których całkowita waga nie przekracza wartości przechowywanej w zmiennej pojemnosc, a których całkowita wartość jest największa wśród możliwych wypełnień plecaka rzeczami o takiej wadze, która nie przekracza wartości zmiennej pojemnosc; pakujemy po jednej sztuce przedmiotu każdego rodzaju

• całkowita wartość spakowanego plecaka

Zaprezentowane rozwiązania będziemy testować dla następujących danych:

• maksymalna pojemność plecaka wynosi 21;

• do dyspozycji mamy po jednej sztuce przedmiotu każdego rodzaju;

• przedmioty mają następujące wartości oraz wagi:

Pojemność plecaka to 21.

Decyzyjny problem plecakowy wymaga, by każdy przedmiot był dodawany do plecaka maksymalnie jeden raz. W programie wymaga to zmiany niewielkiej części programu.

Konieczne jest pominięcie pętli while w tym fragmencie i wykorzystanie instrukcji warunkowej if:

for i in range(n):
	indeks = indeksy[i]
	if wagi[indeks] <= pojemnosc:
		pojemnosc -= wagi[indeks]
		wynik += wartosci[indeks]
		print("Spakowano przedmiot " + nazwy[indeks] + " (indeks " + str(indeks) + ")"

Zwróć uwagę, że w kodzie nie pojawia się również tablica spakowane, ponieważ w przypadku problemu decyzyjnego nie ma potrzeby liczenia, ile sztuk danego przedmiotu spakowano (do dyspozycji jest tylko jedna sztuka danego przedmiotu).

Oto kompletny kod programu:

def sortuj(wartoscDoWagi, indeksy, n):
    for i in range(n - 1):
        for j in range(n - i - 1):
            if wartoscDoWagi[j] < wartoscDoWagi[j + 1]:
                wartoscDoWagi[j], wartoscDoWagi[j + 1] = wartoscDoWagi[j + 1], wartoscDoWagi[j]
                indeksy[j], indeksy[j + 1] = indeksy[j + 1], indeksy[j]

def decyzyjnyPlecak(nazwy, wartosci, wagi, n, pojemnosc):
    wartoscDoWagi = []
    indeksy = []
    for i in range(n):
        wartoscDoWagi.append(wartosci[i] / wagi[i])
        indeksy.append(i)

    sortuj(wartoscDoWagi, indeksy, n)
          
    wynik = 0
    spakowane = []
    for i in range(n):
        spakowane.append(0)

    for i in range(n):
        indeks = indeksy[i]
        if wagi[indeks] <= pojemnosc:
            pojemnosc -= wagi[indeks]
            wynik += wartosci[indeks]
            print("Spakowano przedmiot " + nazwy[indeks] + " (indeks " + str(indeks) + ")")

    print("\nWartosc spakowanych przedmiotow:", wynik)

nazwy = ["aparat", "baterie", "czajnik", "dmuchany materac", "ekologiczny prysznic", "filtr", "garnuszek"]
wartosci = [4, 15, 6,13, 5, 12, 3]
wagi = [8, 3, 2, 6, 15, 16, 2]
n = 7
pojemnosc = 21
decyzyjnyPlecak(nazwy, wartosci, wagi, n, pojemnosc)

Wynik działania programu

Spakowano przedmiot baterie (indeks 1)
Spakowano przedmiot czajnik (indeks 2)
Spakowano przedmiot dmuchany materac (indeks 3)
Spakowano przedmiot garnuszek (indeks 6)
Spakowano przedmiot aparat (indeks 0)

Wartosc spakowanych przedmiotow: 41

Słownik