TechCodeview

Här är ryggsäcken som en behållare eller en påse. Anta att vi har gett några föremål som har en viss vikt eller vinst. Vi måste lägga några föremål i ryggsäcken på ett sådant sätt att totalvärdet ger maximal vinst.

Till exempel är behållarens vikt 20 kg. Vi måste välja föremålen på ett sådant sätt att summan av föremålens vikt antingen ska vara mindre än eller lika med containerns vikt, och vinsten ska vara maximal.

Det finns två typer av ryggsäcksproblem:

• 0/1 knapsack problem
• Problem med fraktionerad ryggsäck

Vi kommer att diskutera båda problemen en efter en. Först kommer vi att lära oss om 0/1 ryggsäcksproblemet.

Vad är problemet med 0/1 ryggsäck?

0/1 ryggsäcksproblemet innebär att föremålen antingen är helt eller inga föremål i en ryggsäck. Till exempel har vi två artiklar som väger 2 kg respektive 3 kg. Om vi ​​väljer föremålet på 2 kg kan vi inte välja föremålet på 1 kg från föremålet på 2 kg (föremålet är inte delbart); vi måste plocka varan på 2 kg helt. Detta är ett 0/1 ryggsäcksproblem där vi antingen plockar varan helt eller så väljer vi den. 0/1 ryggsäcksproblemet löses av den dynamiska programmeringen.

Vad är problemet med fraktionerad ryggsäck?

Problemet med fraktionerad ryggsäck gör att vi kan dela upp föremålet. Till exempel har vi en vara på 3 kg då kan vi plocka varan på 2 kg och lämna varan på 1 kg. Problemet med fraktionerad ryggsäck löses med den giriga metoden.

Exempel på 0/1 ryggsäcksproblem.

Tänk på att problemet med vikter och vinster är:

Vikter: {3, 4, 6, 5}

Vinster: {2, 3, 1, 4}

Ryggsäckens vikt är 8 kg

Antalet föremål är 4

Ovanstående problem kan lösas genom att använda följande metod:

x_i= {1, 0, 0, 1}

= {0, 0, 0, 1}

våren boot arkitektur

= {0, 1, 0, 1}

Ovanstående är möjliga kombinationer. 1 anger att varan är helt plockad och 0 betyder att ingen vara är plockad. Eftersom det finns 4 objekt så kommer möjliga kombinationer att vara:

2⁴= 16; Så. Det finns 16 möjliga kombinationer som kan göras genom att använda ovanstående problem. När alla kombinationer är gjorda måste vi välja den kombination som ger maximal vinst.

En annan metod för att lösa problemet är dynamisk programmering. I ett dynamiskt programmeringssätt delas det komplicerade problemet in i delproblem, sedan hittar vi lösningen på ett delproblem och lösningen av delproblemet kommer att användas för att hitta lösningen på ett komplext problem.

Hur kan detta problem lösas genom att använda den dynamiska programmeringsmetoden?

Först,

vi skapar en matris som visas nedan:

I matrisen ovan representerar kolumner vikten, d.v.s. 8. Raderna representerar artiklars vinster och vikter. Här har vi inte tagit vikten 8 direkt, problemet är uppdelat i delproblem, dvs 0, 1, 2, 3, 4, 5, 6, 7, 8. Lösningen av delproblemen skulle sparas i celler och svaret på problemet skulle lagras i den sista cellen. Först skriver vi vikterna i stigande ordning och vinster enligt deras vikter enligt nedan:

I_i= {3, 4, 5, 6}

sid_i= {2, 3, 4, 1}

Den första raden och den första kolumnen skulle vara 0 eftersom det inte finns något objekt för w=0

När i=1, W=1

I₁= 3; Eftersom vi bara har ett föremål i setet med vikt 3, men ryggsäckens kapacitet är 1. Vi kan inte fylla föremålet på 3 kg i ryggsäcken med kapacitet 1 kg, så lägg till 0 vid M[1][1] som visas nedan :

När i = 1, är W = 2

I₁= 3; Eftersom vi bara har ett föremål i uppsättningen med vikt 3, men ryggsäckens kapacitet är 2. Vi kan inte fylla föremålet på 3 kg i ryggsäcken med kapacitet 2 kg, så lägg till 0 vid M[1][2] som visas nedan :

När i=1, W=3

I₁= 3; Eftersom vi bara har ett föremål i setet med vikt lika med 3, och ryggsäckens vikt är också 3; därför kan vi fylla ryggsäcken med en vikt som är lika med 3. Vi sätter vinst som motsvarar vikten 3, dvs. 2 vid M[1][3] som visas enligt nedan:

När i=1, W = 4

_W1= 3; Eftersom vi bara har ett föremål i setet med vikt lika med 3, och ryggsäckens vikt är 4; därför kan vi fylla ryggsäcken med en vikt som är lika med 3. Vi sätter vinst som motsvarar vikten 3, dvs. 2 vid M[1][4] som visas enligt nedan:

När i=1, W = 5

_W1= 3; Eftersom vi bara har ett föremål i setet med vikt lika med 3, och ryggsäckens vikt är 5; därför kan vi fylla ryggsäcken med en vikt som är lika med 3. Vi sätter vinst som motsvarar vikten 3, dvs. 2 vid M[1][5] som visas enligt nedan:

När i =1, W=6

_W1= 3; Eftersom vi bara har ett föremål i setet med vikt lika med 3, och ryggsäckens vikt är 6; därför kan vi fylla ryggsäcken med en vikt som är lika med 3. Vi sätter vinst som motsvarar vikten 3, dvs. 2 vid M[1][6] som visas enligt nedan:

När i=1, W = 7

_W1= 3; Eftersom vi bara har ett föremål i setet med vikt lika med 3, och ryggsäckens vikt är 7; därför kan vi fylla ryggsäcken med en vikt som är lika med 3. Vi sätter vinst som motsvarar vikten 3, dvs. 2 vid M[1][7] som visas enligt nedan:

När i = 1, är W = 8

_W1= 3; Eftersom vi bara har ett föremål i setet med vikt lika med 3, och ryggsäckens vikt är 8; därför kan vi fylla ryggsäcken med en vikt som är lika med 3. Vi sätter vinst som motsvarar vikten 3, dvs. 2 vid M[1][8] som visas enligt nedan:

Nu ökas värdet på 'i' och blir 2.

När i =2 är W = 1

Vikten som motsvarar värdet 2 är 4, dvs w₂= 4. Eftersom vi bara har ett föremål i setet med vikt lika med 4, och ryggsäckens vikt är 1. Vi kan inte lägga föremålet med vikt 4 i en ryggsäck, så vi lägger till 0 vid M[2][1 ] visas som nedan:

När i =2, W = 2

Vikten som motsvarar värdet 2 är 4, dvs w₂= 4. Eftersom vi bara har ett föremål i setet med vikt lika med 4, och ryggsäckens vikt är 2. Vi kan inte lägga föremålet med vikt 4 i en ryggsäck, så vi lägger till 0 vid M[2][2 ] visas som nedan:

När i =2, W = 3

Vikten som motsvarar värdet 2 är 4, dvs w₂= 4. Eftersom vi har två föremål i setet med vikterna 3 och 4, och ryggsäckens vikt är 3. Vi kan lägga föremålet med vikt 3 i en ryggsäck, så vi lägger till 2 vid M[2][3] visas som nedan:

När i =2 är W = 4

Vikten som motsvarar värdet 2 är 4, dvs w₂= 4. Eftersom vi har två föremål i setet med vikterna 3 och 4, och ryggsäckens vikt är 4. Vi kan lägga föremål med vikt 4 i en ryggsäck eftersom vinsten motsvarande vikt 4 är mer än föremålet med vikt 3, så vi lägger till 3 vid M[2][4] som visas enligt nedan:

När i = 2 är W = 5

Vikten som motsvarar värdet 2 är 4, dvs w₂= 4. Eftersom vi har två föremål i setet med vikterna 3 och 4, och ryggsäckens vikt är 5. Vi kan lägga föremål med vikt 4 i en ryggsäck och vinsten som motsvarar vikten är 3, så vi lägger till 3 vid M[2][5] visas enligt nedan:

När i = 2 är W = 6

Vikten som motsvarar värdet 2 är 4, dvs w₂= 4. Eftersom vi har två föremål i setet med vikterna 3 och 4, och ryggsäckens vikt är 6. Vi kan lägga föremål med vikt 4 i en ryggsäck och vinsten som motsvarar vikten är 3, så vi lägger till 3 vid M[2][6] visas enligt nedan:

När i = 2 är W = 7

Vikten som motsvarar värdet 2 är 4, dvs w₂= 4. Eftersom vi har två föremål i setet med vikterna 3 och 4, och ryggsäckens vikt är 7. Vi kan lägga föremål med vikt 4 och 3 i en ryggsäck och vinsten som motsvarar vikterna är 2 och 3; därför är den totala vinsten 5, så vi lägger till 5 vid M[2][7] som visas enligt nedan:

När i = 2 är W = 8

Vikten som motsvarar värdet 2 är 4, dvs w₂= 4. Eftersom vi har två föremål i setet med vikterna 3 och 4, och ryggsäckens vikt är 7. Vi kan lägga föremål med vikt 4 och 3 i en ryggsäck och vinsten som motsvarar vikterna är 2 och 3; därför är den totala vinsten 5, så vi lägger till 5 vid M[2][7] som visas enligt nedan:

Nu ökas värdet på 'i' och blir 3.

När i = 3 är W = 1

java xor

Vikten som motsvarar värdet 3 är 5, dvs w₃= 5. Eftersom vi har tre föremål i setet med vikterna 3, 4 och 5, och ryggsäckens vikt är 1. Vi kan inte lägga någon av föremålen i en ryggsäck, så vi lägger till 0 vid M[3][ 1] visas som nedan:

När i = 3 är W = 2

Vikten som motsvarar värdet 3 är 5, dvs w₃= 5. Eftersom vi har tre föremål i setet med vikten 3, 4 och 5, och ryggsäckens vikt är 1. Vi kan inte lägga någon av föremålen i en ryggsäck, så vi lägger till 0 vid M[3][ 2] visas som nedan:

När i = 3 är W = 3

Vikten som motsvarar värdet 3 är 5, dvs w₃= 5. Eftersom vi har tre föremål i setet med vikt 3, 4 respektive 5 och ryggsäckens vikt är 3. Föremålet med vikt 3 kan läggas i ryggsäcken och vinsten som motsvarar föremålet är 2, så vi lägger till 2 vid M[3][3] som visas enligt nedan:

När i = 3 är W = 4

Vikten som motsvarar värdet 3 är 5, dvs w₃= 5. Eftersom vi har tre föremål i uppsättningen vikt 3, 4 respektive 5, och ryggsäckens vikt är 4. Vi kan behålla föremålet med antingen vikt 3 eller 4; vinsten (3) som motsvarar vikten 4 är mer än vinsten som motsvarar vikten 3 så vi lägger till 3 vid M[3][4] som visas enligt nedan:

När i = 3 är W = 5

Vikten som motsvarar värdet 3 är 5, dvs w₃= 5. Eftersom vi har tre föremål i uppsättningen vikt 3, 4 respektive 5, och ryggsäckens vikt är 5. Vi kan behålla föremålet med antingen vikt 3, 4 eller 5; vinsten (3) som motsvarar vikten 4 är mer än vinsten som motsvarar vikten 3 och 5, så vi lägger till 3 vid M[3][5] som visas enligt nedan:

När i =3, W = 6

Vikten som motsvarar värdet 3 är 5, dvs w₃= 5. Eftersom vi har tre föremål i uppsättningen vikt 3, 4 respektive 5, och ryggsäckens vikt är 6. Vi kan behålla föremålet med antingen vikt 3, 4 eller 5; vinsten (3) som motsvarar vikten 4 är mer än vinsten som motsvarar vikten 3 och 5, så vi lägger till 3 vid M[3][6] som visas enligt nedan:

När i =3, W = 7

Vikten som motsvarar värdet 3 är 5, dvs w₃= 5. Eftersom vi har tre föremål i uppsättningen vikt 3, 4 respektive 5, och ryggsäckens vikt är 7. I det här fallet kan vi behålla både föremålen med vikt 3 och 4, summan av vinsten skulle vara lika med (2 + 3), d.v.s. 5, så vi lägger till 5 vid M[3][7] som visas enligt nedan:

När i = 3 är W = 8

fmovies Indien

Vikten som motsvarar värdet 3 är 5, dvs w₃= 5. Eftersom vi har tre föremål i uppsättningen vikt 3, 4 respektive 5, och ryggsäckens vikt är 8. I det här fallet kan vi behålla både föremålen med vikt 3 och 4, summan av vinsten skulle vara lika med (2 + 3), d.v.s. 5, så vi lägger till 5 vid M[3][8] som visas enligt nedan:

Nu ökas värdet på 'i' och blir 4.

När i = 4 är W = 1

Vikten som motsvarar värdet 4 är 6, dvs w₄= 6. Eftersom vi har fyra föremål i uppsättningen vikter 3, 4, 5 respektive 6, och ryggsäckens vikt är 1. Vikten av alla föremål är mer än ryggsäckens vikt, så vi kan inte lägg till något föremål i ryggsäcken; Därför lägger vi till 0 vid M[4][1] som visas enligt nedan:

När i = 4 är W = 2

Vikten som motsvarar värdet 4 är 6, dvs w₄= 6. Eftersom vi har fyra föremål i uppsättningen vikter 3, 4, 5 respektive 6, och ryggsäckens vikt är 2. Vikten av alla föremål är mer än ryggsäckens vikt, så vi kan inte lägg till något föremål i ryggsäcken; Därför lägger vi till 0 vid M[4][2] som visas enligt nedan:

När i = 4 är W = 3

Vikten som motsvarar värdet 4 är 6, dvs w₄= 6. Eftersom vi har fyra föremål i uppsättningen vikter 3, 4, 5 respektive 6, och ryggsäckens vikt är 3. Föremålet med vikt 3 kan läggas i ryggsäcken och vinsten motsvarar vikt 4 är 2, så vi lägger till 2 vid M[4][3] som visas enligt nedan:

När i = 4 är W = 4

Vikten som motsvarar värdet 4 är 6, dvs w₄= 6. Eftersom vi har fyra föremål i uppsättningen vikter 3, 4, 5 respektive 6, och ryggsäckens vikt är 4. Föremålet med vikt 4 kan läggas i ryggsäcken och vinsten motsvarar vikt 4 är 3, så vi lägger till 3 vid M[4][4] som visas enligt nedan:

När i = 4 är W = 5

Vikten som motsvarar värdet 4 är 6, dvs w₄= 6. Eftersom vi har fyra föremål i uppsättningen vikter 3, 4, 5 respektive 6, och ryggsäckens vikt är 5. Föremålet med vikt 4 kan läggas i ryggsäcken och vinsten motsvarar vikt 4 är 3, så vi lägger till 3 vid M[4][5] som visas enligt nedan:

När i = 4 är W = 6

Vikten som motsvarar värdet 4 är 6, dvs w₄= 6. Eftersom vi har fyra föremål i uppsättningen vikter 3, 4, 5 respektive 6, och ryggsäckens vikt är 6. I det här fallet kan vi lägga föremålen i ryggsäcken antingen med vikt 3, 4 , 5 eller 6 men vinsten, d.v.s. 4 svarande mot vikten 6 är högst bland alla poster; därför lägger vi till 4 vid M[4][6] som visas enligt nedan:

När i = 4 är W = 7

Vikten som motsvarar värdet 4 är 6, dvs w₄= 6. Eftersom vi har fyra föremål i uppsättningen vikter 3, 4, 5 respektive 6, och ryggsäckens vikt är 7. Här, om vi lägger till två föremål med vikterna 3 och 4, kommer det att producera det maximala vinst, dvs (2 + 3) är lika med 5, så vi lägger till 5 vid M[4][7] som visas enligt nedan:

När i = 4 är W = 8

Vikten som motsvarar värdet 4 är 6, dvs w₄= 6. Eftersom vi har fyra föremål i uppsättningen med vikterna 3, 4, 5 respektive 6, och ryggsäckens vikt är 8. Om vi ​​lägger till två föremål med vikterna 3 och 4 här kommer det att producera det maximala vinst, dvs (2 + 3) är lika med 5, så vi lägger till 5 vid M[4][8] som visas enligt nedan:

Som vi kan observera i tabellen ovan att 5 är den maximala vinsten bland alla poster. Pekaren pekar på den sista raden och den sista kolumnen har 5 värde. Nu ska vi jämföra 5-värdet med föregående rad; om föregående rad, dvs i = 3 innehåller samma värde 5 så kommer pekaren att flyttas uppåt. Eftersom föregående rad innehåller värdet 5 så kommer pekaren att flyttas uppåt som visas i tabellen nedan:

Återigen kommer vi att jämföra värdet 5 från ovanstående rad, dvs i = 2. Eftersom raden ovan innehåller värdet 5 så kommer pekaren återigen att flyttas uppåt som visas i tabellen nedan:

Återigen kommer vi att jämföra värdet 5 från ovanstående rad, dvs i = 1. Eftersom raden ovan inte innehåller samma värde så kommer vi att betrakta raden i=1, och vikten som motsvarar raden är 4. Därför , vi har valt vikten 4 och vi har avvisat vikterna 5 och 6 som visas nedan:

x = { 1, 0, 0}

Vinsten som motsvarar vikten är 3. Därför är den återstående vinsten (5 - 3) lika med 2. Nu ska vi jämföra detta värde 2 med raden i = 2. Eftersom raden (i = 1) innehåller värdet 2 ; därför flyttade pekaren uppåt som visas nedan:

Återigen jämför vi värdet 2 med en ovanstående rad, dvs i = 1. Eftersom raden i =0 inte innehåller värdet 2, så kommer rad i = 1 att väljas och vikten som motsvarar i = 1 visas 3 Nedan:

X = {1, 1, 0, 0}

Vinsten som motsvarar vikten är 2. Därför är den återstående vinsten 0. Vi jämför 0-värdet med raden ovan. Eftersom ovanstående rad innehåller ett 0-värde men vinsten som motsvarar denna rad är 0. I denna uppgift väljs två vikter, d.v.s. 3 och 4 för att maximera vinsten.