In het knapsack-probleem beschouwt men
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.
Schrijf een Python-function knapsack
die een algoritme via branch-and-bound implementeert voor het knapsack-probleem.
>>> 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])