Dynamisch programmeren voor het Integer Knapsack Problem

In het knapsack-probleem beschouwt men n objecten met gegeven gewichten w₀, …, w_n-1 en gegeven winsten p₀, …, p_n-1. Verder is ook de totale capaciteit M van de rugzak gegeven. Er wordt gevraagd om een subset van objecten te selecteren met een zo groot mogelijke totale winst, zodat het totale gewicht de capaciteit niet overschrijdt. In tegenstelling tot het rationale knapsack-probleem, is het bij het discrete knapsack-probleem niet toegelaten om objecten gedeeltelijk te selecteren.

In het specifieke geval dat alle gewichten en de capaciteit gehele getallen zijn, is het mogelijk om dit probleem op te lossen via dynamisch programmeren. De input die hier meegeleverd werd, voldoet aan deze extra vereiste.

Opgave

Schrijf een Python-function knapsackDP die een algoritme via dynamisch programmeren implementeert voor het discrete knapsack-probleem waarbij de gewichten en capaciteit gehele getallen zijn.

Voorbeelden

>>> w1 = [86, 44, 83, 52, 76, 97, 83, 49, 77, 72]
>>> p1 = [803.0, 305.0, 413.0, 778.0, 851.0, 949.0, 957.0, 420.0, 719.0, 913.0]
>>> M1 = 500
>>> knapsackDP(M1, w1, p1)
(5441.0, [0, 3, 4, 6, 7, 8, 9])

>>> w2 = [54, 99, 77, 48, 10, 61, 31, 30, 90, 100]
>>> p2 = [624.0, 518.0, 982.0, 323.0, 811.0, 112.0, 209.0, 473.0, 432.0, 195.0]
>>> M2 = 250
>>> knapsackDP(M2, w2, p2)
(3422.0, [0, 2, 3, 4, 6, 7])