In het knapsack-probleem beschouwt men \(n\) objecten met gegeven gewichten \(g_0\), …, \(g_{n-1}\) en gegeven winsten \(w_0\), …, \(w_{n-1}\). Verder is ook de totale capaciteit \(M\) van de knapsack gegeven. Er wordt gevraagd om een deelverzameling van objecten te selecteren met een zo groot mogelijke totale winst, zodat het totale gewicht de capaciteit niet overschrijdt.

In de discrete versie van het knapsack probleem is het niet toegestaan om objecten gedeeltelijk te selecteren. Dit lijkt misschien een klein verschil in vergelijking met de rationale versie, maar maakt het probleem veel moeilijker. Het discrete probleem is NP-compleet terwijl de rationale versie optimaal opgelost kan worden met een eenvoudig gretig algoritme. Gelukkig kunnen we hetzelfde idee ook gebruiken om voor het discrete probleem een branch-and-bound algoritme op te stellen dat heel wat kan snoeien.

Opgave

Schrijf een Python-function knapsack die een algoritme via branch-and-bound implementeert voor het knapsack-probleem.

Voorbeelden

>>> w01 = [16.0, 79.0, 29.0, 83.0, 36.0, 43.0, 40.0, 21.0, 57.0, 83.0, 21.0, 71.0, 27.0, 65.0, 37.0, 92.0, 35.0, 35.0, 81.0, 16.0]
>>> p01 = [258.0, 458.0, 770.0, 901.0, 757.0, 1000.0, 499.0, 642.0, 969.0, 539.0, 544.0, 722.0, 703.0, 564.0, 164.0, 930.0, 690.0, 378.0, 772.0, 238.0]
>>> M01 = 400.0
>>> knapsack(M01, w01, p01)
(7554.0, [0, 2, 4, 5, 6, 7, 8, 10, 11, 12, 16])

>>> w02 = [23.0, 20.0, 45.0, 89.0, 44.0, 89.0, 37.0, 90.0, 30.0, 99.0, 86.0, 57.0, 46.0, 80.0, 95.0, 85.0, 33.0, 44.0, 86.0, 97.0]
>>> p02 = [977.0, 588.0, 836.0, 652.0, 358.0, 265.0, 625.0, 702.0, 927.0, 894.0, 192.0, 300.0, 901.0, 252.0, 133.0, 628.0, 397.0, 253.0, 305.0, 501.0]
>>> M02 = 400.0
>>> knapsack(M02, w02, p02)
(6503.0, [0, 1, 2, 4, 6, 8, 9, 12, 16])