Kontinuerligt ryggsäcksproblem

Inom teoretisk datavetenskap är det kontinuerliga ryggsäcksproblemet (även känt som det fraktionella ryggsäcksproblemet ) ett algoritmiskt problem i kombinatorisk optimering där målet är att fylla en behållare ("knapsäcken") med fraktionerade mängder av olika material som valts för att maximera värdet av de valda materialen. Det liknar det klassiska ryggsäcksproblemet , där föremålen som ska placeras i behållaren är odelbara; dock kan det kontinuerliga ryggsäcksproblemet lösas i polynomtid medan det klassiska ryggsäcksproblemet är NP-hårt . Det är ett klassiskt exempel på hur en till synes liten förändring i formuleringen av ett problem kan ha stor inverkan på dess beräkningskomplexitet .

Problemdefinition

Ett exempel på antingen de kontinuerliga eller klassiska ryggsäcksproblemen kan specificeras av ryggsäckens numeriska kapacitet W , tillsammans med en samling material, som vart och ett har två siffror associerade med sig: vikten w _i av material som är tillgängligt för valt och det totala värdet v _i för det materialet. Målet är att välja en mängd x _i ≤ w _i av varje material, med förbehåll för kapacitetsbegränsningen

$$\sum _{i}x_{i}\leq W$$

och maximera den totala nyttan

$$\sum _{i}x_{i}v_{i}.$$

måste var och en av mängderna x _{i vara antingen noll eller} w _i ; det kontinuerliga ryggsäcksproblemet skiljer sig genom att låta x _i sträcka sig kontinuerligt från noll till w _i .

Vissa formuleringar av detta problem skalar om variablerna x _i till att ligga i intervallet från 0 till 1. I detta fall blir kapacitetsbegränsningen

$$\sum _{i}x_{i}w_{i}\leq W,$$

och målet är att maximera den totala nyttan

$$\sum _{i}x_{i}v_{i}.$$

Lösningsteknik

Det kontinuerliga ryggsäcksproblemet kan lösas med en girig algoritm , först publicerad 1957 av George Dantzig , som betraktar materialen i sorterad ordning efter deras värden per viktenhet. För varje material väljs mängden x _{i så stor som möjligt:}

• Om summan av de val som gjorts hittills är lika med kapaciteten W , så sätter algoritmen x _i = 0.
• Om skillnaden d mellan summan av de val som gjorts hittills och W är mindre än w _i , så sätter algoritmen x _i = d .
• I det återstående fallet väljer algoritmen x _i = w _i .

På grund av behovet av att sortera materialen tar denna algoritm tid O ( n log n ) på ingångar med n material. Men genom att anpassa en algoritm för att hitta viktade medianer är det möjligt att lösa problemet i tid O ( n ).