Fractional knapsack op basis van verhouding

Je hebt items met een waarde en een gewicht, plus een tas met beperkte capaciteit. Het doel is om zoveel mogelijk totale waarde mee te nemen. 🎒

In de fractionele variant mag je een deel van een item meenemen, bijvoorbeeld een halve zak graan. Die vrijheid zorgt ervoor dat greedy hier werkt.

De belangrijkste maatstaf is de verhouding tussen de waarde en het gewicht van elk item. Een hoge verhouding betekent veel waarde in weinig ruimte.

Sorteer items op waarde per gewicht, van hoog naar laag. De greedy-aanpak blijft steeds de beschikbare waarde met de hoogste dichtheid nemen.

Doorloop de gesorteerde lijst en neem elk item volledig mee als het nog in de resterende capaciteit past. Tel de volledige waarde ervan op bij je totaal.

Als een item te groot is, neem je een deel dat de resterende ruimte precies vult. Daarna is de tas vol en stop je.

Elke capaciteitseenheid moet zoveel mogelijk waarde bevatten, dus het item met de hoogste dichtheid moet eerst komen. Een lagere dichtheid inruilen kost alleen maar waarde.

Als voorwerpen niet kunnen worden opgesplitst, werkt de gulzige methode op basis van de verhouding niet. Voor de 0/1-versie heb je dynamisch programmeren nodig, niet deze eenvoudige sortering.

Sorteren op verhouding kost O(n log n) en de vul-lus is lineair. Dat is ruim snel genoeg voor gebruikelijke limieten bij programmeerwedstrijden.

Gebruik zwevende komma's of exacte rationale getallen voor het gedeeltelijke voorwerp. Vroeg afkappen kan waarde verloren laten gaan en een fout antwoord veroorzaken.

Denk aan het laden van vracht, het mengen van brandstoffen of het verdelen van grondstoffen. Zodra onderdelen deelbaar zijn, is de gulzige methode op basis van de verhouding je gereedschap.

Sorteer voorwerpen op waarde per gewicht, neem hele voorwerpen zolang ze passen en neem daarna een fractie om de tas helemaal te vullen. Deze gulzige methode is alleen optimaal als je voorwerpen kunt opsplitsen. 🚀