i den här handledningen har vi tidigare diskuterat fraktionellt Knapsackproblem med girig tillvägagångssätt. Vi har visat att girig inställning ger en optimal lösning för fraktionerad ryggsäck. Detta kapitel kommer dock att omfatta 0-1 ryggsäck problem och dess analys.
I 0-1 ryggsäck, objekt kan inte brytas vilket innebär att tjuven ska ta objektet som helhet eller bör lämna den., Detta är anledningen till att kalla det som 0-1 ryggsäck.
i händelse av 0-1 ryggsäck kan värdet av xi vara antingen 0 eller 1, där andra begränsningar förblir desamma.
0-1 ryggsäck kan inte lösas genom girig strategi. Giriga tillvägagångssätt säkerställer inte en optimal lösning. I många fall kan girig inställning ge en optimal lösning.
följande exempel kommer att fastställa vårt uttalande.
exempel-1
låt oss överväga att ryggsäckens kapacitet är w = 25 och posterna är som visas i följande tabell.,
| objekt | a | b | c | d |
|---|---|---|---|---|
| vinst | 24 | 18 | 18 | 10 |
| vikt | 24 | 10 | 10 | 7 |
utan att överväga vinsten per enhetsvikt (pi/Wi), om vi tillämpar giriga tillvägagångssätt för att lösa detta problem, kommer första objektet a att väljas eftersom det kommer att bidra med maximal vinst bland alla element.,
Efter att ha valt objekt A, kommer inga fler objekt att väljas. Därför, för denna givna uppsättning poster total vinst är 24. Den optimala lösningen kan uppnås genom att välja objekt, B och C, där den totala vinsten är 18 + 18 = 36.
exempel-2
istället för att välja objekten baserat på den totala fördelen, väljs objekten i det här exemplet baserat på förhållandet pi / wi. Låt oss överväga att ryggsäckens kapacitet är w = 60 och objekten är som visas i följande tabell.,
| Item | A | B | C |
|---|---|---|---|
| Price | 100 | 280 | 120 |
| Weight | 10 | 40 | 20 |
| Ratio | 10 | 7 | 6 |
Using the Greedy approach, first item A is selected. Then, the next item B is chosen. Hence, the total profit is 100 + 280 = 380., Den optimala lösningen av denna instans kan dock uppnås genom att välja objekt, B och C, där den totala vinsten är 280 + 120 = 400.
därför kan man dra slutsatsen att girig inställning kanske inte ger en optimal lösning.
För att lösa 0-1 ryggsäck krävs dynamisk programmeringsmetod.
Problem uttalande
en tjuv rånar en butik och kan bära en maximal vikt av W i sin ryggsäck. Det finns n-objekt och vikt av ith-objektet är wi och vinsten att välja det här objektet är pi. Vilka saker ska tjuven ta?,
Dynamic-Programming Approach
Låt mig vara det högst numrerade objektet i en optimal lösning S för W-Dollar. Då är S ’ = S – {i} en optimal lösning för W-Wi-dollar och värdet på lösningen S är vi plus värdet på delproblemet.
Vi kan uttrycka detta faktum i följande formel: definiera C för att vara lösningen för objekt 1,2,…, i och den maximala vikten w.,
algoritmen tar följande ingångar
-
den maximala vikten W
-
antalet objekt n
-
de två sekvenserna v = <v1, v2, …, vn> och w = <W1, W2, …, WN>
uppsättningen objekt att ta kan härledas från tabellen, börjar vid C och spårar bakåt där de optimala värdena kom ifrån.
analys
denna algoritm tar θ(n, w) gånger som tabell C har (n + 1).(w + 1) poster, där varje post kräver θ (1) tid att beräkna.,