Problem plecakowy
Lekcja 7 z 15 w kursie Programowanie dynamiczne — podstawy w Coddy.
Problem plecakowy to klasyczny problem optymalizacyjny w informatyce. Treść problemu jest prosta: mając zbiór przedmiotów, z których każdy ma określoną wagę i wartość, określ, które przedmioty należy umieścić w kolekcji, tak aby łączna waga była mniejsza lub równa danemu limitowi, a łączna wartość była maksymalna.
Istnieją dwa rodzaje problemu plecakowego:
- Problem plecakowy 0/1: w tej wersji złodziej nie może zabierać części przedmiotu — albo zabiera go w całości, albo go zostawia.
- Problem plecakowy z podziałem: w tej wersji złodziej może zabierać części przedmiotu, czyli może zabrać jego część.
Wyzwanie
ŚredniNapisz funkcję o nazwie knapsack, która rozwiązuje problem plecakowy 0/1. Funkcja powinna przyjmować trzy dane wejściowe:
- Listę wag n przedmiotów (w1, w2, ... , wn).
- Listę wartości n przedmiotów (v1, v2, ... , vn).
- Maksymalną ładowność plecaka (W).
Funkcja powinna następnie zwrócić maksymalną wartość, jaką można uzyskać, wypełniając plecak.
Na przykład:
weights = [10, 20, 30]
values = [60, 100, 120]
W = 50
knapsack(weights, values, W)Wynik:
220 # taking the 2 largest itemsSpróbuj swoich sił
def knapsack(wrights, values, W):
# Napisz kod tutajWszystkie lekcje w sekcji Programowanie dynamiczne — podstawy
1Wprowadzenie do programowania dynamicznego
Czym jest programowanie dynamiczne?Dlaczego jest ważne?Zastosowania w różnych dziedzinach4Zaawansowane zagadnienia
Minimalna długość podtablicyPrzycinanieOptymalizacja pamięciMaskowanie bitów3Algorytmy programowania dynamicznego
Najdłuższy wspólny podciągProblem plecakowyProblem wydawania resztyOdległość edycyjnaPoćwicz samodzielnie: Kompilator Python online