Fraktionell ryggsäck efter kvot

Ni har objekt med ett värde och en vikt samt en väska med begränsad kapacitet. Målet är att bära så stort sammanlagt värde som möjligt. 🎒

I den fraktionella varianten får ni ta en del av ett objekt, till exempel en halv säck spannmål. Det är denna frihet som gör att en girig algoritm fungerar här.

Det viktiga måttet är varje objekts kvot mellan värde och vikt. En hög kvot innebär att mycket värde ryms på väldigt liten plats.

Sortera objekten efter värde per vikt, med högst kvot först. Den giriga planen är att hela tiden välja det tillgängliga objektet med högst värdetäthet.

Gå igenom den sorterade listan och ta varje objekt helt om det fortfarande får plats i den återstående kapaciteten. Lägg till hela dess värde i totalsumman.

När ett objekt är för stort tar ni den andel som exakt fyller det återstående utrymmet. Därefter är väskan full och ni slutar.

Varje kapacitetsenhet bör innehålla så mycket värde som möjligt, så objektet med högst värdetäthet måste väljas först. Att byta in lägre täthet minskar bara värdet.

Om objekt inte kan delas upp fungerar det inte att vara girig utifrån kvoten. 0/1-versionen kräver dynamisk programmering, inte den här enkla sorteringen.

Att sortera efter kvot kostar O(n log n), och ifyllnadsslingan är linjär. Det är mer än tillräckligt snabbt för typiska tävlingsgränser.

Använd flyttal eller exakta rationella tal för den del av objektet som tas delvis. Om värdet trunkeras för tidigt kan en del av värdet gå förlorad och ge fel svar.

Tänk på att lasta frakt, blanda bränslen eller dela upp resurser. När delar kan delas upp är den giriga kvotmetoden rätt verktyg.

Sortera objekten efter värde per viktenhet, ta hela objekt så länge de får plats och fyll sedan på med en del av nästa objekt. Den här giriga metoden är bara optimal när objekten kan delas upp. 🚀