Een reeks items zijn genummerd van $$0$$ t.e.m. $$N-1$$, en worden gekenmerkt door hun massa en waarde. Je beschikt over een tas die qua draagvermogen massa $$M$$ heeft. De vraag is dus welke items je meeneemt, zodat de totale waarde van de tasinhoud zo groot mogelijk is.

We noemen $$m_i$$ de massa van item met rangnummer $$i$$ en $$w_i$$ de bijhorende waarde. De hulpvariabelen $$r_i$$ (i tussen 0 en $$N-1$$, grenzen inbegrepen) nemen enkel de waarden 0 of 1 aan, en geven aan of het item met rangnummer $$i$$ al dan niet in de tas gestopt wordt. Het probleem kan dan wiskundig geformuleerd worden als:

Zoek de variabelen $$r_i$$ zodat $$\sum_{i=0}^{N-1} r_i w_i$$
maximaal wordt, waarbij : $$\sum_{i=0}^{N-1} r_i m_i \le M$$

In deze oefening bouwen we een reeks klassen die het mogelijk maken om dit probleem via een aantal strategieën aan te pakken.

Klasse Item

een constructor me twee argumenten, namelijk de massa en de waarde van het item (in die volgorde)

de methode `__str__()` levert de stringgedaante '(massa,waarde)'. Deze stringgedaante bevat geen spaties.

de operator < vertoont volgend gedrag voor de uitdrukking a < b:

• we bepalen de waarde per massaeenheid als de verhouding tussen de waarde en de massa van $$a$$ en $$b$$. Noem deze verhoudingen $$v_a$$ en $$v_b$$
• indien $$|v_a - v_b| < 10^{-10}$$ dan levert a < b als resultaat True indien de massa van $$a$$ strikt groter is dan de massa van $$b$$. Het resultaat is False in het andere geval.
• indien $$|v_a - v_b| >= 10^{-10}$$ dan levert a < b als resultaat True indien $$v_a > v_b$$ en False in het andere geval.

Voorbeeld

item1 = Item(3,1)
item2 = Item(10,7)
print(item1) #(3,1)
print(item2) #(10,7)
item1 < item2 #False
item2 < item1 #True

Klasse TasProbleem

Een object van deze klasse stelt een probleemstelling voor, gekenmerkt dus door het draagvermogen van de te vullen tas en de items waaruit genomen kan worden. Programmeer in deze klasse:

• een constructor met 1 argument (een strikt positief geheel getal), het maximale draagvermogen van de tas
• de operator += met als linkeroperand een object van de klasse TasProbleem
  • indien het rechteroperand een object van de klasse Item is, dan wordt dit object toegevoegd een lijst van items waartussen gekozen kan worden om de tas te vullen
  • indien het rechteroperand een lijst is, dan worden alle objecten uit die lijst die van de klasse Item zijn, toegevoegd aan de lijst van objecten waartussen gekozen kan worden om de tas te vullen (andere objecten worden genegeerd).
  Alle items krijgen een rangnummer (startend bij 0) in de volgorde waarin ze toegevoegd werden.
• de methode `__str__()` levert als stringgedaante '(draagvermogen,[i0,i1,...])' (zonder aanhalingstekens, zonder spaties), waarbij i0 voor de stringgedaante van het item met rangnummer 0 voorstelt (analoog voor alle andere items).
• de methode massa_waarde() met 1 argument, namelijk een lijst van binaire waarden $$r$$. Deze methode levert als resultaat een tuple $$(m,w)$$ met :
  • $$m = w = -1$$ indien de lengte van $$r$$ niet overeenstemt met het aantal items waaruit gekozen kan worden, of $$r$$ een element bevat verschillend van 0 of 1
  • in alle andere gevallen wordt $$m$$ de totale massa van de tas indien de items gekozen worden conform $$r$$, en idem voor $$w$$ die de bijhorende waarde voorstelt.
• de methode vul_tas() heeft 1 argument, namelijk een object over een methode vul() beschikt. Het enige argument van de methode vul() is een object van de klasse TasProbleem. Het resultaat van de methode vul_tas() is lijst bestaande uit tuples. Elk van die tuples stelt een oplossing voor (niet noodzakelijk optimaal), die verkregen werd door beroep te doen op de methode vul() van het argumentobject. Elk tuple bestaat uit 3 componenten, namelijk:
  • de lijst van de variabelen $$r_i$$ (dus een lijst van waarden 0 of 1 die evenveel elementen bevat als er items te kiezen zijn)
  • de totale massa in de tas aanwezig, indien ze volgens deze variabelen gevuld wordt
  • de totale waarde van de tas, indien ze volgens deze variabelen gevuld wordt

Voorbeeld

tp = TasProbleem(31)
for (m, w) in zip([1, 9, 5, 1, 6, 7, 1],[8, 9, 5, 6, 2, 10, 1]):
	tp += Item(m, w)
print(tp)	#(31,[(1,8),(9,9),(5,5),(1,6),(6,2),(7,10),(1,1)])
l = [Item(m, w) for (m, w) in zip([4, 9, 5, 1, 10, 4],[4, 9, 3, 10, 5, 6])]
tp += l
print(tp) #(31,[(1,8),(9,9),(5,5),(1,6),(6,2),(7,10),(1,1),(4,4),(9,9),(5,3),(1,10),(10,5),(4,6)])
tp.massa_waarde([0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1]) #(13, 27)
tp.massa_waarde([1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0]) #(24, 25)

Elk van onderstaande klassen beschikt over de methode vul() met als enig argument een object van de klasse TasProbleem. Het resultaat van de methode is een lijst van gesuggereerde oplossingen, waarbij elke oplossing de vorm aanneemt van een lijst $$r$$ bestaande uit nullen en enen. De lijst $$r$$ bevat evenveel elementen als er items kunnen gekozen worden. Let erop dat de indices van de lijst $$r$$ overeenkomen met de ORIGINELE volgorde van de items in het tasprobleem (dus de volgorde van toevoegen). De strategieën EenvoudigeStrategie en GulzigeStrategie leveren steeds 1 oplossing op (de methode vul() levert dus een lijst van 1 element, namelijk 1 lijst $$r$$), terwijl de strategie UitputtendeStrategie meerdere oplossingen kan genereren (dus mogelijks een lijst met meer dan 1 lijst $$r$$).

De tekst hieronder beschrijft telkens de te volgen strategie bij het genereren van oplossingen voor het tasprobleem.

EenvoudigeStrategie

Beschouw de items in de volgorde waarin ze toegevoegd werden aan het probleem. We stoppen items in de tas in de gegeven volgorde, en doen dit tot het draagvermogen van de tas overschreden zou worden, mochten we het volgende item toevoegen. Alle items die volgen worden dan niet verder beschouwd. Er is op die manier 1 oplossing te construeren.

GulzigeStrategie

Sorteer alle items die voor selectie in aanmerking komen volgens de operator < uit de klasse Item. Beschouw alle items in die volgorde, en stop items in de tas, voor zover het draagvermogen van de tas niet overschreden wordt. Beschouw ALLE elementen die voor keuze in aanmerking komen (en stop de iteratie dus niet zodra je een element ontmoet dat niet kan toegevoegd worden, maar beschouw ook alle volgende items). Er is op die manier 1 oplossing te construeren. Let erop dat indices in de oplossing verwijzen naar items in de ORIGINELE volgorde (dus voor het sorteren).

UitputtendeStrategie

Hier beschouwen we alle oplossingen $$r$$ die voldoen aan de randvoorwaarde dat de totale massa het draagvermogen van de tas niet mag overschrijden. Selecteer onder al die oplossingen de oplossingen die de waarde maximaal maken (er kunnen dus meerdere oplossingen aanleiding geven tot dezelfde maximale waarde). Er is op die manier MINSTENS 1 oplossing te construeren. Sorteer de lijst van alle oplossingen via de ingebouwde sorted() functie vooraleer ze als resultaat terug te geven.

Voorbeeld

tp = TasProbleem(38)
for (m, w) in zip([8, 10, 6, 9, 4, 9, 1, 6, 8, 9, 7],[1, 4, 4, 2, 3, 5, 1, 7, 5, 7, 9]):
	tp += Item(m, w)
print(tp) #(38,[(8,1),(10,4),(6,4),(9,2),(4,3),(9,5),(1,1),(6,7),(8,5),(9,7),(7,9)])
eenvoudig = EenvoudigeStrategie()
eenvoudig.vul(tp) #[[1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0]]
gulzig = GulzigeStrategie()
gulzig.vul(tp) #[[0, 0, 1, 0, 1, 0, 1, 1, 0, 1, 1]]
uitputtend = UitputtendeStrategie() 
uitputtend.vul(tp) #[[0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1], [0, 0, 1, 0, 0, 1, 1, 1, 0, 1, 1]]
tp.vul_tas(eenvoudig) #[([1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0], 37, 14)]
tp.vul_tas(gulzig) #[([0, 0, 1, 0, 1, 0, 1, 1, 0, 1, 1], 33, 31)]
tp.vul_tas(uitputtend) #[([0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1], 37, 33), ([0, 0, 1, 0, 0, 1, 1, 1, 0, 1, 1], 38, 33)]