Fractional Knapsack

Q: Jak rozwiązać problem ułamkowego plecaka bez użycia liczb zmiennoprzecinkowych?

Przy dodatnich wagach test a / b > c / d jest równoważny testowi a × d > c × b , więc porównuj gęstości, mnożąc na krzyż. Najlepsza wartość to liczba całkowita plus jeden ułamek, values[i] × room / weights[i] dla przedmiotu, który jest ucinany, więc jedno dzielenie całkowite daje dokładnie zaokrąglony w dół wynik.

ŚrednieAlgorytmy zachłanne Sortowanie

+10

Masz n przedmiotów. Przedmiot i jest wart values[i] i waży weights[i]. Twój plecak może pomieścić łącznie najwyżej capacity jednostek wagi, a każdy przedmiot możesz zabrać w dowolnej części: kawałek przedmiotu i ważący w jest wart values[i] × w / weights[i].

Napisz funkcję o nazwie fractionalKnapsack, która zwraca największą łączną wartość, jaką może pomieścić plecak, zaokrągloną w dół do liczby całkowitej.

Funkcja

fractionalKnapsack(values: integer-array, weights: integer-array, capacity: integer) → integer

valuesinteger-array: wartość każdego przedmiotu
weightsinteger-array: waga każdego przedmiotu
capacityinteger: maksymalna waga, jaką może pomieścić torba
Zwracainteger: największa łączna wartość, która mieści się w plecaku, zaokrąglona w dół

Ograniczenia

1 ≤ n ≤ 5000, gdzie n = values.length = weights.length
1 ≤ values[i], weights[i] ≤ 10⁴
1 ≤ capacity ≤ 10⁸

Przykłady

Wejście: values = [40, 90, 30, 50]weights = [8, 30, 5, 20]capacity = 40
Wyjście: 151
Wyjaśnienie: W przeliczeniu na jednostkę masy przedmioty są warte 5, 3, 6 i 2.5. Przedmioty 2 i 0 mieszczą się w całości, dając 70, a pozostaje miejsce na 27. Dodanie 27 z 30 jednostek przedmiotu 1 daje 81, czyli łącznie 151.

Wejście: values = [10, 7]weights = [4, 3]capacity = 5
Wyjście: 12
Wyjaśnienie: Przedmiot 0 jest wart 2,5 za jednostkę, a przedmiot 1 około 2,33, więc przedmiot 0 trafia w całości do plecaka i daje 10. Jedna z 3 jednostek przedmiotu 1 dodaje 7 / 3, a 12 i jedna trzecia zaokrągla się w dół do 12.

Pytanie dodatkowe

Czy potrafisz znaleźć odpowiedź w czasie O(n), bez sortowania wszystkich elementów?

Podpowiedzi

Otwieraj je po kolei. Każda zdradza trochę więcej.

Otwarte: 0 z 3

Rozwiązanie

Ponieważ możesz dzielić przedmioty, jest to problem zachłanny, w przeciwieństwie do problemu plecakowego 0/1: każda jednostka wagi powinna pochodzić z przedmiotu o największej pozostałej wartości na jednostkę wagi. Posortuj przedmioty według tej gęstości i wkładaj je do plecaka w tej kolejności. Porównuj gęstości, mnożąc na krzyż, a zaokrąglaj w dół tylko ilość odcinanego przedmiotu, tak aby nigdy nie przechowywać ułamka.

Wybieraj najgęstszy przedmiot w każdej rundzie

Poprawne, ale nie kończy się na największych testach

Intuicja

Napełniaj plecak, zaczynając od przedmiotu o największej gęstości: weź go w całości, jeśli się zmieści, a w przeciwnym razie weź część, która wypełni plecak, i zakończ. Znajdź najgęstszy niewykorzystany przedmiot, skanując wszystkie i porównując values[i] × weights[j] z values[j] × weights[i] zamiast dzielenia. Przy dodatnich wagach to ten sam test, a oba iloczyny nie przekraczają 10^8.

Najlepiej zacząć od przedmiotów o największej gęstości: jeśli ładunek zawiera pewną wagę mniej gęstego przedmiotu, a gęstszy przedmiot nie został jeszcze w pełni dodany, zamiana tej wagi na gęstszy przedmiot nie może obniżyć wartości. Powtarzaj zamiany, aż uzyskasz ładunek z przedmiotami ułożonymi od najgęstszego.

Wykonuje się do n rund, a każda skanuje niewykorzystane przedmioty — około n²/2 = 12.5 miliona porównań dla n = 5000.

Algorytm

Oznacz każdy przedmiot jako niewykorzystany i ustaw room = capacity oraz total = 0.
Gdy jest jeszcze miejsce, przejrzyj niewykorzystane przedmioty i znajdź ten o największej gęstości, porównując gęstości przez mnożenie na krzyż.
Jeśli nie ma już żadnego przedmiotu, zatrzymaj się. W przeciwnym razie oznacz ten przedmiot jako wykorzystany.
Jeśli się mieści, dodaj jego wartość do total, a jego wagę odejmij od room. Jeśli się nie mieści, dodaj values[i] × room / weights[i], stosując dzielenie całkowite, i zatrzymaj się.
Zwróć total.

def fractionalKnapsack(values, weights, capacity):
    n = len(values)
    used = [False] * n
    total = 0
    room = capacity
    while room > 0:
        best = -1
        for i in range(n):
            # i is denser than best: values[i] / weights[i] > values[best] / weights[best], cross-multiplied
            if not used[i] and (best == -1 or values[i] * weights[best] > values[best] * weights[i]):
                best = i
        if best == -1:
            break  # every item is already in the bag
        used[best] = True
        if weights[best] <= room:
            total += values[best]
            room -= weights[best]
        else:
            total += values[best] * room // weights[best]  # the part that fits, rounded down
            room = 0
    return total

Sortuj według wartości na jednostkę wagi

Intuicja

Skanowanie za każdym razem znajduje przedmiot o największej gęstości, ale kolejność nie zmienia się między kolejnymi rundami. Posortuj przedmioty raz, zaczynając od tych o największej gęstości, używając tego samego porównania z mnożeniem krzyżowym. Przedmioty o takiej samej gęstości mogą wystąpić w dowolnej kolejności, ponieważ ich wartość na jednostkę jest taka sama.

Dodawaj całe przedmioty, dopóki się mieszczą. Pierwszy, który się nie zmieści, jest jedynym, który dzielisz: jego wartość to values[i] × room / weights[i], a dzielenie całkowite zaokrągla wynik w dół. Wszystko przed nim jest liczbą całkowitą, więc zaokrąglenie tego jednego składnika daje dokładny wynik. Sortowanie kosztuje O(n log n), a przejście O(n).

Algorytm

Utwórz listę indeksów elementów i posortuj je od najgęstszego, używając porównania przez mnożenie krzyżowe.
Ustaw room = capacity i total = 0.
Dla każdego elementu w tej kolejności, jeśli weights[i] ≤ room, dodaj jego wartość i odejmij jego wagę od room.
W przeciwnym razie dodaj values[i] × room / weights[i] z dzieleniem całkowitoliczbowym i zakończ.
Zwróć total.

from functools import cmp_to_key


def fractionalKnapsack(values, weights, capacity):
    # a goes before b when values[a] / weights[a] > values[b] / weights[b],
    # tested as values[a] * weights[b] > values[b] * weights[a] to stay in whole numbers.
    def denser_first(a, b):
        return values[b] * weights[a] - values[a] * weights[b]

    order = sorted(range(len(values)), key=cmp_to_key(denser_first))
    total = 0
    room = capacity
    for i in order:
        if weights[i] <= room:
            total += values[i]  # the whole item fits
            room -= weights[i]
        else:
            total += values[i] * room // weights[i]  # the part that fits, rounded down
            break
    return total

Pułapki i przypadki brzegowe

Sortowanie wyłącznie według wartości lub wagi. W pierwszym przykładzie przedmiot o wartości 90 zajmuje dopiero trzecie miejsce pod względem gęstości; wybranie go jako pierwszego pozostawia miejsce na połowę przedmiotu o wartości 50, co daje 115 zamiast 151.
Dzielenie przed mnożeniem. Dla wartości 13, wagi 7 i miejsca na 3, 13 / 7 * 3 w arytmetyce całkowitoliczbowej daje 3, a 13 * 3 / 7 daje prawidłowy wynik 5.
Zakładanie, że za każdym razem trzeba przeciąć jakiś przedmiot. W trzecim przykładzie mieszczą się wszystkie przedmioty, a odpowiedzią jest suma ich wartości, czyli 13.

Najczęstsze pytania3

Jaka jest złożoność czasowa problemu plecakowego z ułamkami?

Posortowanie przedmiotów według wartości na jednostkę masy kosztuje O(n log n), a wypełnianie wymaga jednego przejścia, więc łączna złożoność wynosi O(n log n), a na kolejność potrzeba O(n) pamięci. Wyszukiwanie przedmiotu o największej gęstości w każdej rundzie kosztuje O(n²).

Dlaczego algorytm zachłanny działa dla problemu plecakowego ułamkowego, ale nie dla problemu plecakowego 0/1?

Dzielenie pozwala zamienić wagę mniej gęstego przedmiotu na bardziej gęsty. Bez dzielenia gęsty przedmiot może pozostawić miejsce, którego nic innego nie wypełni. Przy wartościach 8, 11, 15, wagach 2, 3, 4 i pojemności 7, wybór najpierw najgęstszych przedmiotów daje wagi 2 i 4, czyli 23, podczas gdy wagi 3 i 4 dają 26. Wersja 0/1 wymaga programowania dynamicznego.

Jak rozwiązać problem ułamkowego plecaka bez użycia liczb zmiennoprzecinkowych?

Przy dodatnich wagach test a / b > c / d jest równoważny testowi a × d > c × b, więc porównuj gęstości, mnożąc na krzyż. Najlepsza wartość to liczba całkowita plus jeden ułamek, values[i] × room / weights[i] dla przedmiotu, który jest ucinany, więc jedno dzielenie całkowite daje dokładnie zaokrąglony w dół wynik.

def fractionalKnapsack(values, weights, capacity):
    # Wpisz kod tutaj

Test #1

Test #2

Test #3

Argumenty

values = [40, 90, 30, 50]
weights = [8, 30, 5, 20]
capacity = 40

Oczekiwany wynik