Biorąc pod uwagę zestaw przedmiotów, każdy o wadze i wartości, określ liczbę każdego elementu do uwzględnienia w kolekcji, aby całkowita waga była mniejsza lub równa danemu limitowi, a całkowita wartość była tak duża, jak to możliwe.

Wikipedia, aby uzyskać więcej informacji

Na przykład możesz otrzymać maksymalną wagę 15 i obiektów o wartości / masach jako, [5,2], [7,4] [1,1]a wynik byłby równy [7,0,1]7 [5 <value>, 2 <mass>]obiektom i 1 [1 <value>, 1 <mass>]obiektowi z wynikiem 36.

Zasady

Dane wejściowe można przyjmować w dowolnym rozsądnym formacie

Dane wyjściowe mają również elastyczny format,

Nie wolno używać bibliotek niestandardowych. Jeśli musisz zainstalować lub pobrać dowolną bibliotekę, aby używać jej oddzielnie od początkowej konfiguracji, nie jest to dozwolone

Obiekty mogą mieć masę ujemną i wartość (tj. -1, -1)

Wymagane optymalne odpowiedzi

Zwycięski

Najkrótszy kod wygrywa

Ujemna masa i wartość?

To kluczowa część tego wyzwania. Powiedzmy, że masz obiekt z przedmiotami (masa, wartość), takimi jak [4,3],[-1,-1]torba o pojemności 15. Możesz umieścić 3 z pierwszych i zdobyć 9 lub umieścić 4 z pierwszych i jeden z -1, -1 obiekt za wynik 11.

Pyth, 18 bajtów

h.MshMZfghQseMTy*F

Dane wyjściowe jako lista par [wartość, waga]. Okropnie nieefektywny, ale jest kompletny NP.
Wypróbuj tutaj

Wyjaśnienie

h.MshMZfghQseMTy*F
               y*FQ  Get all sets with up to <capacity> of each item.
       fghQseMT      Choose the sets whose total weight fits in the bag.
 .MshMZ              Choose those with the highest value.
h                    Take the first.