PYTHON Wielomianowy schemat aproksymacji
Zminimalizuj wagę całkowitą przy maksymalizacji wartości całkowitej
Otrzymujesz zestaw przedmiotów, z których każdy ma określoną wartość i wagę. Twoim zadaniem jest wybranie takiego podzbioru przedmiotów, aby zmaksymalizować wartość całkowitą przy jednoczesnym utrzymaniu wagi całkowitej poniżej danej pojemności. Jednak w tym przypadku chcemy zminimalizować całkowitą wagę spośród wszystkich możliwych rozwiązań, które osiągają maksymalną wartość.
Dane wejściowe:
Lista elementów, gdzie każdy element jest reprezentowany przez krotkę (wartość, waga).
Maksymalna pojemność wagowa plecaka.
Wyjście:
Podzbiór elementów, który maksymalizuje całkowitą wartość przy jednoczesnej minimalizacji całkowitej wagi.
Przykład:
Wejście:
items = [(10, 3), (8, 2), (5, 1), (12, 5), (6, 4)]
capacity = 8
Wyjście:
selected_items = [(8, 2), (5, 1)]
total_weight = 3
total_value = 13
Zminimalizuj wagę całkowitą przy maksymalizacji wartości całkowitej
Otrzymujesz zestaw przedmiotów, z których każdy ma określoną wartość i wagę. Twoim zadaniem jest wybranie takiego podzbioru przedmiotów, aby zmaksymalizować wartość całkowitą przy jednoczesnym utrzymaniu wagi całkowitej poniżej danej pojemności. Jednak w tym przypadku chcemy zminimalizować całkowitą wagę spośród wszystkich możliwych rozwiązań, które osiągają maksymalną wartość.
Dane wejściowe:
Lista elementów, gdzie każdy element jest reprezentowany przez krotkę (wartość, waga).
Maksymalna pojemność wagowa plecaka.
Wyjście:
Podzbiór elementów, który maksymalizuje całkowitą wartość przy jednoczesnej minimalizacji całkowitej wagi.
Przykład:
Wejście:
items = [(10, 3), (8, 2), (5, 1), (12, 5), (6, 4)]
capacity = 8
Wyjście:
selected_items = [(8, 2), (5, 1)]
total_weight = 3
total_value = 13
Odpowiedź:
Odpowiedź w załączniku.
Pozdrawiam ciebie oraz życzę miłego dnia