Przeczytaj

Implementacja rozwiązania ogólnego problemu plecakowego wykorzystującego programowanie dynamiczneprogramowanie dynamiczneprogramowanie dynamiczne – język Python

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
poj – 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 poj, 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 poj
całkowita wartość spakowanego plecaka

Zaczynamy od zapisania nagłówka funkcji ogolny_problem_plecakowy_dynamiczne. Przyjmuje pięć argumentów:

wagi – tablica liczb naturalnych; tablica wag przedmiotów;
wartosci – tablica liczb naturalnych; tablica wartości przedmiotów;
nazwy – tablica łańcuchów znaków; nazwy przedmiotów;
n – liczba naturalna; liczba dostępnych przedmiotów;
poj – liczba naturalna; pojemność plecaka.

def ogolny_problem_plecakowy_dynamiczne(wagi, wartosci, nazwy, n, poj):

Tworzymy dwie tablice – P oraz Q. Długość obu tablic wynosi poj + 1, wypełniamy je zerami.

Tablica P przechowuje maksymalne wartości, jakie można osiągnąć dla różnych pojemności plecaka, a tablica Q przechowuje informacje o indeksach przedmiotów, które zostały spakowane dla danej pojemności.

def ogolny_problem_plecakowy_dynamiczne(wagi, wartosci, nazwy, n, poj):
    P = [0] * (poj + 1)
    Q = [0] * (poj + 1)

Zapisujemy dwie pętle for. Pierwsza z nich iteruje przez wszystkie przedmioty, druga (zagnieżdżona) iteruje przed wszystkie możliwe pojemności plecaka.

def ogolny_problem_plecakowy_dynamiczne(wagi, wartosci, nazwy, n, poj):
    P = [0] * (poj + 1)
    Q = [0] * (poj + 1)

    for i in range(n):
        for j in range(1, poj + 1):

Sprawdzamy, czy aktualnie rozważany przedmiot może być spakowany do plecaka o danej pojemności j, czyli czy jego waga jest mniejsza lub równa wartości i-tego elementu tablicy wagi.

def ogolny_problem_plecakowy_dynamiczne(wagi, wartosci, nazwy, n, poj):
    P = [0] * (poj + 1)
    Q = [0] * (poj + 1)

    for i in range(n):
        for j in range(1, poj + 1):
            if wagi[i] <= j:

Dla każdego przedmiotu sprawdzamy, czy jego waga jest mniejsza lub równa aktualnej pojemności plecaka. Jeśli tak, to porównujemy maksymalną wartość dla aktualnej pojemności plecaka z wartością uzyskaną przez dodanie aktualnego przedmiotu. Jeśli wartość uzyskana przez dodanie przedmiotu jest większa, aktualizujemy wartość w tablicy P na pozycji j oraz indeks w tablicy Q.

def ogolny_problem_plecakowy_dynamiczne(wagi, wartosci, nazwy, n, poj):
    P = [0] * (poj + 1)
    Q = [0] * (poj + 1)

    for i in range(n):
        for j in range(1, poj + 1):
            if wagi[i] <= j:
                if P[j] < P[j - wagi[i]] + wartosci[i]:
                    P[j] = P[j - wagi[i]] + wartosci[i]
                    Q[j] = i + 1

Po obliczeniu wartości dla wszystkich możliwych kombinacji przedmiotów i pojemności plecaka, iterujemy przez tablicę Q, aby określić, które przedmioty zostały spakowane i w jakiej liczbie.

Tworzymy listę spakowane_przedmioty, która będzie przechowywać liczbę spakowanych sztuk każdego przedmiotu. Inicjalizujemy ją wartościami zero, ponieważ na początku jeszcze nie spakowaliśmy żadnego przedmiotu.

Inicjalizujemy zmienną pojemnosc wartością poj, czyli maksymalną pojemnością plecaka. Ta zmienna będzie nam służyć do śledzenia, ile miejsca w plecaku pozostało do zapakowania.

Uruchamiamy pętlę while, która będzie wykonywać się, dopóki wartość zmiennej pojemnosc jest większa od 0, czyli w plecaku jest jeszcze miejsce.

def ogolny_problem_plecakowy_dynamiczne(wagi, wartosci, nazwy, n, poj):
    P = [0] * (poj + 1)
    Q = [0] * (poj + 1)

    for i in range(n):
        for j in range(1, poj + 1):
            if wagi[i] <= j:
                if P[j] < P[j - wagi[i]] + wartosci[i]:
                    P[j] = P[j - wagi[i]] + wartosci[i]
                    Q[j] = i + 1

    spakowane_przedmioty = [0] * n
    pojemnosc = poj
    while pojemnosc > 0:

Sprawdzamy, czy dla aktualnej pojemności pojemnosc istnieje jakiś indeks przedmiotu w tablicy Q (czyli czy został spakowany jakiś przedmiot). Jeśli tak, przechodzimy do kolejnego kroku.

def ogolny_problem_plecakowy_dynamiczne(wagi, wartosci, nazwy, n, poj):
    P = [0] * (poj + 1)
    Q = [0] * (poj + 1)

    for i in range(n):
        for j in range(1, poj + 1):
            if wagi[i] <= j:
                if P[j] < P[j - wagi[i]] + wartosci[i]:
                    P[j] = P[j - wagi[i]] + wartosci[i]
                    Q[j] = i + 1

    spakowane_przedmioty = [0] * n
    pojemnosc = poj
    while pojemnosc > 0:
        if Q[pojemnosc] != 0:

Zwiększamy licznik spakowanych sztuk dla przedmiotu o indeksie Q[pojemnosc] - 1. Indeks ten wskazuje na przedmiot, który został spakowany dla aktualnej pojemności pojemnosc.

def ogolny_problem_plecakowy_dynamiczne(wagi, wartosci, nazwy, n, poj):
    P = [0] * (poj + 1)
    Q = [0] * (poj + 1)

    for i in range(n):
        for j in range(1, poj + 1):
            if wagi[i] <= j:
                if P[j] < P[j - wagi[i]] + wartosci[i]:
                    P[j] = P[j - wagi[i]] + wartosci[i]
                    Q[j] = i + 1

    spakowane_przedmioty = [0] * n
    pojemnosc = poj
    while pojemnosc > 0:
        if Q[pojemnosc] != 0:
            spakowane_przedmioty[Q[pojemnosc] - 1] += 1

Zmniejszamy wartość pojemnosc o wagę przedmiotu, który został spakowany dla aktualnej pojemności pojemnosc. Dzięki temu symulujemy usunięcie spakowanego przedmiotu z plecaka, aby sprawdzić, ile miejsca pozostało do zapakowania kolejnych przedmiotów.

def ogolny_problem_plecakowy_dynamiczne(wagi, wartosci, nazwy, n, poj):
    P = [0] * (poj + 1)
    Q = [0] * (poj + 1)

    for i in range(n):
        for j in range(1, poj + 1):
            if wagi[i] <= j:
                if P[j] < P[j - wagi[i]] + wartosci[i]:
                    P[j] = P[j - wagi[i]] + wartosci[i]
                    Q[j] = i + 1

    spakowane_przedmioty = [0] * n
    pojemnosc = poj
    while pojemnosc > 0:
        if Q[pojemnosc] != 0:
            spakowane_przedmioty[Q[pojemnosc] - 1] += 1
        pojemnosc -= wagi[Q[pojemnosc] - 1]

Na końcu wypisujemy informacje o spakowanych przedmiotach oraz łączną wartość spakowanych przedmiotów.

Dodajemy wywołanie funkcji.

Kompletny kod:

Linia 1. def ogolny podkreślnik problem podkreślnik plecakowy podkreślnik dynamiczne otwórz nawias okrągły wagi przecinek wartosci przecinek nazwy przecinek n przecinek poj zamknij nawias okrągły dwukropek. Linia 2. P znak równości otwórz nawias kwadratowy 0 zamknij nawias kwadratowy asterysk otwórz nawias okrągły poj plus 1 zamknij nawias okrągły. Linia 3. Q znak równości otwórz nawias kwadratowy 0 zamknij nawias kwadratowy asterysk otwórz nawias okrągły poj plus 1 zamknij nawias okrągły. Linia 5. for i in range otwórz nawias okrągły n zamknij nawias okrągły dwukropek. Linia 6. for j in range otwórz nawias okrągły 1 przecinek poj plus 1 zamknij nawias okrągły dwukropek. Linia 7. if wagi otwórz nawias kwadratowy i zamknij nawias kwadratowy otwórz nawias ostrokątny znak równości j dwukropek. Linia 8. if P otwórz nawias kwadratowy j zamknij nawias kwadratowy otwórz nawias ostrokątny P otwórz nawias kwadratowy j minus wagi otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias kwadratowy plus wartosci otwórz nawias kwadratowy i zamknij nawias kwadratowy dwukropek. Linia 9. P otwórz nawias kwadratowy j zamknij nawias kwadratowy znak równości P otwórz nawias kwadratowy j minus wagi otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias kwadratowy plus wartosci otwórz nawias kwadratowy i zamknij nawias kwadratowy. Linia 10. Q otwórz nawias kwadratowy j zamknij nawias kwadratowy znak równości i plus 1. Linia 12. spakowane podkreślnik przedmioty znak równości otwórz nawias kwadratowy 0 zamknij nawias kwadratowy asterysk n. Linia 13. pojemnosc znak równości poj. Linia 14. while pojemnosc zamknij nawias ostrokątny 0 dwukropek. Linia 15. if Q otwórz nawias kwadratowy pojemnosc zamknij nawias kwadratowy wykrzyknik znak równości 0 dwukropek. Linia 16. spakowane podkreślnik przedmioty otwórz nawias kwadratowy Q otwórz nawias kwadratowy pojemnosc zamknij nawias kwadratowy minus 1 zamknij nawias kwadratowy plus znak równości 1. Linia 17. pojemnosc minus znak równości wagi otwórz nawias kwadratowy Q otwórz nawias kwadratowy pojemnosc zamknij nawias kwadratowy minus 1 zamknij nawias kwadratowy. Linia 19. print otwórz nawias okrągły cudzysłów Liczba spakowanych sztuk przedmiotów dwukropek cudzysłów zamknij nawias okrągły. Linia 20. for i in range otwórz nawias okrągły n zamknij nawias okrągły dwukropek. Linia 21. print otwórz nawias okrągły nazwy otwórz nawias kwadratowy i zamknij nawias kwadratowy plus cudzysłów otwórz nawias okrągły indeks cudzysłów plus str otwórz nawias okrągły i zamknij nawias okrągły plus cudzysłów zamknij nawias okrągły dwukropek cudzysłów plus str otwórz nawias okrągły spakowane podkreślnik przedmioty otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias okrągły zamknij nawias okrągły. Linia 23. print otwórz nawias okrągły cudzysłów Wartość spakowanych przedmiotów dwukropek cudzysłów plus str otwórz nawias okrągły P otwórz nawias kwadratowy poj zamknij nawias kwadratowy zamknij nawias okrągły zamknij nawias okrągły. Linia 26. wagi znak równości otwórz nawias kwadratowy 1 przecinek 2 przecinek 2 zamknij nawias kwadratowy. Linia 27. wartosci znak równości otwórz nawias kwadratowy 1 przecinek 4 przecinek 5 zamknij nawias kwadratowy. Linia 28. nazwy znak równości otwórz nawias kwadratowy cudzysłów aparat cudzysłów przecinek cudzysłów bukłak cudzysłów przecinek cudzysłów chlebak cudzysłów zamknij nawias kwadratowy. Linia 29. n znak równości len otwórz nawias okrągły wagi zamknij nawias okrągły. Linia 30. poj znak równości 5. Linia 32. ogolny podkreślnik problem podkreślnik plecakowy podkreślnik dynamiczne otwórz nawias okrągły wagi przecinek wartosci przecinek nazwy przecinek n przecinek poj zamknij nawias okrągły.

def ogolny_problem_plecakowy_dynamiczne(wagi, wartosci, nazwy, n, poj):
    P = [0] * (poj + 1)
    Q = [0] * (poj + 1)

    for i in range(n):
        for j in range(1, poj + 1):
            if wagi[i] <= j:
                if P[j] < P[j - wagi[i]] + wartosci[i]:
                    P[j] = P[j - wagi[i]] + wartosci[i]
                    Q[j] = i + 1

    spakowane_przedmioty = [0] * n
    pojemnosc = poj
    while pojemnosc > 0:
        if Q[pojemnosc] != 0:
            spakowane_przedmioty[Q[pojemnosc] - 1] += 1
        pojemnosc -= wagi[Q[pojemnosc] - 1]

    print("Liczba spakowanych sztuk przedmiotów:")
    for i in range(n):
        print(nazwy[i] + " (indeks " + str(i) + "): " + str(spakowane_przedmioty[i]))

    print("Wartość spakowanych przedmiotów: " + str(P[poj]))


wagi = [1, 2, 2]
wartosci = [1, 4, 5]
nazwy = ["aparat", "bukłak", "chlebak"]
n = len(wagi)
poj = 5

ogolny_problem_plecakowy_dynamiczne(wagi, wartosci, nazwy, n, poj)

Wynik działania programu:

Liczba spakowanych sztuk przedmiotu aparat (indeks 0): 1
Liczba spakowanych sztuk przedmiotu bukłak (indeks 1): 0
Liczba spakowanych sztuk przedmiotu chlebak (indeks 2): 2
Wartość spakowanych przedmiotów: 11

Polecenie 1

Wróć do e‑materiału Problem plecakowy w języku PythonPBdZ2NqknProblem plecakowy w języku Python. Porównaj wyniki działania obu zaprezentowanych programów.

Słownik

memoryzacja

zapamiętywanie wyników mniejszych podproblemów, aby później móc z nich skorzystać przy dalszych etapach rozwiązywania większych podproblemów

nakładające się podproblemy

problem główny składa się z nakładających się podproblemów, jeżeli można go rozbić na podproblemy, które mogą być używane wielokrotnie i które są ze sobą powiązane

problem optymalizacyjny

problem obliczeniowy, którego rozwiązanie polega na znalezieniu największej lub najmniejszej wartości pewnego parametru tego problemu, spełniającej określoną własność

problem plecakowy

problem plecakowy, który jest tematem tej serii e‑materiałów, polega na takim wyborze przedmiotów z danego zbioru, by po spakowaniu wybrane przedmioty miały jak największą wartość, ale ich waga nie przekraczała pojemności plecaka. Istnieją różne metody jego rozwiązania, w tej serii prezentujemy jedną z nich – podejście zachłannemetoda zachłanna algorytmuzachłanne

własność optymalnej podstruktury

problem posiada własność optymalnej podstruktury, jeśli optymalne rozwiązanie głównego problemu można znaleźć na podstawie optymalnych rozwiązań jej podproblemów

metoda „dziel i zwyciężaj”

metoda, która pozwala podzielić zadany problem na mniejsze, łatwiejsze do rozwiązania podproblemy; po rozwiązaniu podproblemów algorytm łączy je z powrotem w całość i rozwiązuje problem główny

metoda zachłanna algorytmu

metoda, w której algorytm dokonuje lokalnie optymalnego wyboru, licząc, że doprowadzi to do znalezienia globalnie optymalnego rozwiązania

NumPy

biblioteka do obliczeń naukowych dla języka Python; oferuje optymalne czasowo działania na tablicach wielowymiarowych; charakteryzuje się zoptymalizowanymi operacjami i algorytmami numerycznymi napisanymi głównie w języku C

programowanie dynamiczne

technika algorytmiczna służąca do rozwiązywania problemu poprzez rozbicie go na mniejsze podproblemy i wykorzystanie faktu, że optymalne rozwiązanie całego problemu zależy od rozwiązania jego podproblemów

Wprowadzenie

Prezentacja multimedialna

Implementacja rozwiązania ogólnego problemu plecakowego wykorzystującego programowanie dynamiczneprogramowanie dynamiczneprogramowanie dynamiczne – język Python

Słownik