Het knapsack-probleem is een probleem uit combinatorische optimalisatie: gegeven een reeks items, elk met een gewicht en een waarde, bepaal het aantal van elk item om op te nemen in een collectie zo dat het totale gewicht niet groter is dan een gegeven limiet, terwijl de totale waarde zo groot mogelijk is. De naam verwijst naar het probleem om een rugzak, beperkt in capaciteit, te vullen met de meeste waardevolle objecten.

De meest voorkomende variant is het 0-1 knapsack-probleem, waarbij het aantal x[i] exemplaren van elk object ofwel nul ofwel een is. Gegeven een reeks van n items genummerd van 0 tot n-1, elk met een gewicht w[i] en een waarde p[i], evenals een maximum gewichtscapaciteit M, moeten we sum(p[i]*x[i] for i in range(n)) maximaliseren, onder de voorwaarden dat sum(w[i]*x[i] for i in range(n)) <= M en x[i] in {0,1}. Hierbij stelt x[i] het aantal exemplaren van item i opgenomen in de knapsack voor.

In het rationale knapsack-probleem is het ook toegestaan om een deel van een object te selecteren.

Ontwerp een optimaal algoritme voor dit probleem met polynomiale uitvoeringstijd. Denk er goed over na of en waarom dit algoritme altijd de optimale selectie vindt en implementeer het.

Opgave

Schrijf een Python-functie knapsack die de capaciteit M van de rugzak als parameter krijgt, evenals een lijst gewichten en een lijst winsten. De functie geeft de totale winst en het totale gewicht van de optimale selectie terug, alsook een lijst met geselecteerde objecten gesorteerd op index van de orginele lijsten (met voor elk geselecteerd object zijn index in de oorspronkelijk gegeven lijst van gewichten/winsten en de fractie waarin het object aan de optimale selectie is toegevoegd).

Voorbeeld

>>> w1 = [86.0, 44.0, 83.0, 52.0, 76.0, 97.0, 83.0, 49.0, 77.0, 72.0]
>>> p1 = [803.0, 305.0, 413.0, 778.0, 851.0, 949.0, 957.0, 420.0, 719.0, 913.0]
>>> M1 = 500.0
>>> knapsack(M1, w1, p1)
(5568.5, 500.0, [(0, 0.5), (3, 1.0), (4, 1.0), (5, 1.0), (6, 1.0), (8, 1.0), (9, 1.0)])

>>> w2 = [54.0, 99.0, 77.0, 48.0, 10.0, 61.0, 31.0, 30.0, 90.0, 100.0]
>>> p2 = [624.0, 518.0, 982.0, 323.0, 811.0, 112.0, 209.0, 473.0, 432.0, 195.0]
>>> M2 = 250.0
>>> knapsack(M2, w2, p2)
(3422.0, 250.0, [(0, 1.0), (2, 1.0), (3, 1.0), (4, 1.0), (6, 1.0), (7, 1.0)])