Her er rygsæk som en beholder eller en pose. Antag, at vi har givet nogle genstande, som har en vis vægt eller overskud. Vi er nødt til at lægge nogle ting i rygsækken på en sådan måde, at den samlede værdi giver maksimal fortjeneste.

For eksempel er beholderens vægt 20 kg. Vi skal udvælge emnerne på en sådan måde, at summen af ​​vægten af ​​emner enten skal være mindre end eller lig med beholderens vægt, og fortjenesten skal være maksimal.

Der er to typer rygsækproblemer:

• 0/1 rygsæk problem
• Fractional rygsæk problem

Vi vil diskutere begge problemer én efter én. Først vil vi lære om 0/1 rygsæk problemet.

Hvad er 0/1 rygsæk problemet?

0/1 rygproblemet betyder, at varerne enten er helt eller ingen varer er fyldt i en rygsæk. For eksempel har vi to varer med en vægt på henholdsvis 2 kg og 3 kg. Hvis vi vælger 2 kg varen, kan vi ikke vælge 1 kg varen fra 2 kg varen (varen er ikke delelig); vi skal vælge varen på 2 kg helt. Dette er et 0/1 rygsækproblem, hvor vi enten vælger varen fuldstændigt, eller også vælger vi den vare. 0/1 rygsæk problemet løses ved den dynamiske programmering.

Hvad er problemet med fraktioneret rygsæk?

Problemet med fraktioneret rygsæk betyder, at vi kan dele varen op. For eksempel har vi en vare på 3 kg, så kan vi vælge varen på 2 kg og lade varen på 1 kg stå. Problemet med fraktioneret rygsæk er løst ved den grådige tilgang.

Eksempel på 0/1 rygsæk problem.

Overvej, at problemet med vægte og overskud er:

Vægte: {3, 4, 6, 5}

Fortjeneste: {2, 3, 1, 4}

Rygsækkens vægt er 8 kg

Antallet af varer er 4

Ovenstående problem kan løses ved at bruge følgende metode:

x_jeg= {1, 0, 0, 1}

= {0, 0, 0, 1}

læse fra csv-fil i java

= {0, 1, 0, 1}

Ovenstående er de mulige kombinationer. 1 angiver, at varen er helt plukket, og 0 betyder, at ingen vare er plukket. Da der er 4 elementer, vil mulige kombinationer være:

2⁴= 16; Så. Der er 16 mulige kombinationer, der kan laves ved at bruge ovenstående problem. Når alle kombinationerne er lavet, skal vi vælge den kombination, der giver den maksimale fortjeneste.

En anden tilgang til at løse problemet er dynamisk programmeringstilgang. I dynamisk programmeringstilgang opdeles det komplicerede problem i delproblemer, derefter finder vi løsningen af ​​et delproblem og løsningen af ​​delproblemet vil blive brugt til at finde løsningen af ​​et komplekst problem.

Hvordan kan dette problem løses ved at bruge den dynamiske programmeringstilgang?

Først,

vi opretter en matrix vist som nedenfor:

I ovenstående matrix repræsenterer kolonner vægten, dvs. 8. Rækkerne repræsenterer overskuddet og vægten af ​​varer. Her har vi ikke taget vægten 8 direkte, problemet er opdelt i delopgaver, dvs. 0, 1, 2, 3, 4, 5, 6, 7, 8. Løsningen af ​​delproblemerne ville blive gemt i celler og svaret på problemet ville blive gemt i den sidste celle. Først skriver vi vægtene i stigende rækkefølge og overskud i henhold til deres vægte vist som nedenfor:

I_jeg= {3, 4, 5, 6}

s_jeg= {2, 3, 4, 1}

Den første række og den første kolonne ville være 0, da der ikke er noget element for w=0

Når i=1, W=1

I₁= 3; Da vi kun har én genstand i sættet med vægt 3, men rygsækkens kapacitet er 1. Vi kan ikke fylde varen på 3 kg i rygsækken med en kapacitet på 1 kg, så tilføj 0 ved M[1][1] vist som nedenfor :

Når i = 1, er W = 2

I₁= 3; Da vi kun har én genstand i sættet med vægt 3, men rygsækkens kapacitet er 2. Vi kan ikke fylde varen på 3 kg i rygsækken med en kapacitet på 2 kg, så tilføj 0 ved M[1][2] vist som nedenfor :

Når i=1, W=3

I₁= 3; Da vi kun har én genstand i sættet med vægt lig med 3, og rygsækkens vægt også er 3; derfor kan vi fylde rygsækken med en vægt svarende til 3. Vi sætter fortjeneste svarende til vægten 3, dvs. 2 ved M[1][3] vist som nedenfor:

Når i=1, W = 4

_W1= 3; Da vi kun har én genstand i sættet med vægt lig med 3, og rygsækkens vægt er 4; derfor kan vi fylde rygsækken med en vægt svarende til 3. Vi sætter fortjeneste svarende til vægten 3, dvs. 2 ved M[1][4] vist som nedenfor:

Når i=1, W = 5

_W1= 3; Da vi kun har én genstand i sættet med vægt lig med 3, og rygsækkens vægt er 5; derfor kan vi fylde rygsækken med en vægt svarende til 3. Vi sætter fortjeneste svarende til vægten 3, dvs. 2 ved M[1][5] vist som nedenfor:

Når i =1, W=6

_W1= 3; Da vi kun har én genstand i sættet med vægt lig med 3, og rygsækkens vægt er 6; derfor kan vi fylde rygsækken med en vægt svarende til 3. Vi sætter fortjeneste svarende til vægten 3, dvs. 2 ved M[1][6] vist som nedenfor:

Når i=1, W = 7

_W1= 3; Da vi kun har én genstand i sættet med vægt lig med 3, og rygsækkens vægt er 7; derfor kan vi fylde rygsækken med en vægt svarende til 3. Vi sætter fortjeneste svarende til vægten 3, dvs. 2 ved M[1][7] vist som nedenfor:

Når i = 1, W = 8

_W1= 3; Da vi kun har én genstand i sættet med vægt lig med 3, og rygsækkens vægt er 8; derfor kan vi fylde rygsækken med en vægt svarende til 3. Vi sætter fortjeneste svarende til vægten 3, dvs. 2 ved M[1][8] vist som nedenfor:

Nu bliver værdien af ​​'i' øget og bliver 2.

Når i =2, er W = 1

Vægten svarende til værdien 2 er 4, dvs. w₂= 4. Da vi kun har én genstand i sættet med vægt lig med 4, og rygsækkens vægt er 1. Vi kan ikke lægge varen med vægt 4 i en rygsæk, så vi tilføjer 0 ved M[2][1 ] vist som nedenfor:

Når i = 2, er W = 2

Vægten svarende til værdien 2 er 4, dvs. w₂= 4. Da vi kun har én genstand i sættet med vægt lig med 4, og rygsækkens vægt er 2. Vi kan ikke lægge varen med vægt 4 i en rygsæk, så vi tilføjer 0 ved M[2][2 ] vist som nedenfor:

Når i = 2, er W = 3

Vægten svarende til værdien 2 er 4, dvs. w₂= 4. Da vi har to emner i sættet med vægt 3 og 4, og rygsækkens vægt er 3. Vi kan lægge emnet med vægt 3 i en rygsæk, så vi tilføjer 2 ved M[2][3] vist som nedenfor:

Når i = 2, er W = 4

Vægten svarende til værdien 2 er 4, dvs. w₂= 4. Da vi har to genstande i sættet med vægt 3 og 4, og rygsækkens vægt er 4. Vi kan lægge vare med vægt 4 i en rygsæk, da fortjenesten svarende til vægt 4 er mere end varen med vægt 3, så vi tilføjer 3 ved M[2][4] vist som nedenfor:

Når i = 2, er W = 5

Vægten svarende til værdien 2 er 4, dvs. w₂= 4. Da vi har to emner i sættet med vægt 3 og 4, og rygsækkens vægt er 5. Vi kan lægge vare med vægt 4 i en rygsæk og fortjenesten svarende til vægt er 3, så vi tilføjer 3 kl. M[2][5] vist som nedenfor:

Når i = 2, er W = 6

Vægten svarende til værdien 2 er 4, dvs. w₂= 4. Da vi har to emner i sættet med vægt 3 og 4, og rygsækkens vægt er 6. Vi kan lægge emne med vægt 4 i en rygsæk, og fortjenesten svarende til vægt er 3, så vi tilføjer 3 kl. M[2][6] vist som nedenfor:

Når i = 2, er W = 7

Vægten svarende til værdien 2 er 4, dvs. w₂= 4. Da vi har to genstande i sættet med vægten 3 og 4, og rygsækkens vægt er 7. Vi kan lægge emnet med vægt 4 og 3 i en rygsæk, og overskuddet svarende til vægten er 2 og 3; derfor er det samlede overskud 5, så vi tilføjer 5 ved M[2][7] vist som nedenfor:

Når i = 2, er W = 8

Vægten svarende til værdien 2 er 4, dvs. w₂= 4. Da vi har to emner i sættet med vægt 3 og 4, og rygsækkens vægt er 7. Vi kan lægge emne med vægt 4 og 3 i en rygsæk, og overskuddet svarende til vægt er 2 og 3; derfor er det samlede overskud 5, så vi tilføjer 5 ved M[2][7] vist som nedenfor:

Nu øges værdien af ​​'i' og bliver 3.

Når i = 3, er W = 1

10 af 60

Vægten svarende til værdien 3 er 5, dvs. w₃= 5. Da vi har tre genstande i sættet med vægten 3, 4 og 5, og rygsækkens vægt er 1. Vi kan ikke lægge nogen af ​​tingene i en rygsæk, så vi tilføjer 0 ved M[3][ 1] vist som nedenfor:

Når i = 3, er W = 2

Vægten svarende til værdien 3 er 5, dvs. w₃= 5. Da vi har tre genstande i sættet med vægten 3, 4 og 5, og rygsækkens vægt er 1. Vi kan ikke lægge nogen af ​​tingene i en rygsæk, så vi tilføjer 0 ved M[3][ 2] vist som nedenfor:

Når i = 3, er W = 3

Vægten svarende til værdien 3 er 5, dvs. w₃= 5. Da vi har tre genstande i sættet af henholdsvis vægt 3, 4 og 5, og rygsækkens vægt er 3. Genstanden med vægt 3 kan lægges i rygsækken, og fortjenesten svarende til varen er 2, så vi tilføjer 2 ved M[3][3] vist som nedenfor:

Når i = 3, er W = 4

Vægten svarende til værdien 3 er 5, dvs. w₃= 5. Da vi har tre genstande i sættet med henholdsvis vægt 3, 4 og 5, og rygsækkens vægt er 4. Vi kan beholde varen med enten vægt 3 eller 4; fortjenesten (3) svarende til vægten 4 er mere end fortjenesten svarende til vægten 3, så vi tilføjer 3 ved M[3][4] vist som nedenfor:

Når i = 3, er W = 5

Vægten svarende til værdien 3 er 5, dvs. w₃= 5. Da vi har tre genstande i sættet med henholdsvis vægt 3, 4 og 5, og rygsækkens vægt er 5. Vi kan beholde varen med enten vægt 3, 4 eller 5; overskuddet (3) svarende til vægten 4 er mere end overskuddet svarende til vægten 3 og 5, så vi tilføjer 3 ved M[3][5] vist som nedenfor:

Når i = 3, er W = 6

Vægten svarende til værdien 3 er 5, dvs. w₃= 5. Da vi har tre genstande i sættet med henholdsvis vægt 3, 4 og 5, og rygsækkens vægt er 6. Vi kan beholde varen med enten vægt 3, 4 eller 5; overskuddet (3) svarende til vægten 4 er mere end overskuddet svarende til vægten 3 og 5, så vi tilføjer 3 ved M[3][6] vist som nedenfor:

Når i =3, W = 7

Vægten svarende til værdien 3 er 5, dvs. w₃= 5. Da vi har tre genstande i sættet med henholdsvis vægt 3, 4 og 5, og rygsækkens vægt er 7. I dette tilfælde kan vi beholde både emnerne med vægt 3 og 4, summen af ​​overskuddet ville være lig med (2 + 3), dvs. 5, så vi tilføjer 5 ved M[3][7] vist som nedenfor:

Når i = 3, er W = 8

c struktur i struktur

Vægten svarende til værdien 3 er 5, dvs. w₃= 5. Da vi har tre emner i sættet med henholdsvis vægt 3, 4 og 5, og rygsækkens vægt er 8. I dette tilfælde kan vi beholde både emnerne med vægt 3 og 4, summen af profit ville være lig med (2 + 3), dvs. 5, så vi tilføjer 5 ved M[3][8] vist som nedenfor:

Nu bliver værdien af ​​'i' øget og bliver 4.

Når i = 4, er W = 1

Vægten svarende til værdien 4 er 6, dvs. w₄= 6. Da vi har fire genstande i vægtsættet henholdsvis 3, 4, 5 og 6, og rygsækkens vægt er 1. Vægten af ​​alle emnerne er mere end rygsækkens vægt, så vi kan ikke tilføje enhver genstand i rygsækken; Derfor tilføjer vi 0 ved M[4][1] vist som nedenfor:

Når i = 4, er W = 2

Vægten svarende til værdien 4 er 6, dvs. w₄= 6. Da vi har fire genstande i vægtsættet henholdsvis 3, 4, 5 og 6, og rygsækkens vægt er 2. Vægten af ​​alle emnerne er mere end rygsækkens vægt, så vi kan ikke tilføje enhver genstand i rygsækken; Derfor tilføjer vi 0 ved M[4][2] vist som nedenfor:

Når i = 4, er W = 3

Vægten svarende til værdien 4 er 6, dvs. w₄= 6. Da vi har fire genstande i vægtsættet hhv. 3, 4, 5 og 6, og rygsækkens vægt er 3. Genstanden med vægt 3 kan lægges i rygsækken, og fortjenesten svarer til vægt 4 er 2, så vi tilføjer 2 ved M[4][3] vist som nedenfor:

Når i = 4, er W = 4

Vægten svarende til værdien 4 er 6, dvs. w₄= 6. Da vi har fire genstande i vægtsættet henholdsvis 3, 4, 5 og 6, og rygsækkens vægt er 4. Genstanden med vægt 4 kan lægges i rygsækken, og fortjenesten svarer til vægt 4 er 3, så vi tilføjer 3 ved M[4][4] vist som nedenfor:

Når i = 4, er W = 5

Vægten svarende til værdien 4 er 6, dvs. w₄= 6. Da vi har fire genstande i vægtsættet henholdsvis 3, 4, 5 og 6, og rygsækkens vægt er 5. Genstanden med vægt 4 kan lægges i rygsækken, og fortjenesten svarer til vægt 4 er 3, så vi tilføjer 3 ved M[4][5] vist som nedenfor:

Når i = 4, er W = 6

Vægten svarende til værdien 4 er 6, dvs. w₄= 6. Da vi har fire genstande i sættet med vægte henholdsvis 3, 4, 5 og 6, og rygsækkens vægt er 6. I dette tilfælde kan vi lægge emnerne i rygsækken enten med vægt 3, 4 , 5 eller 6 men fortjenesten, dvs. 4 svarende til vægten 6, er højest blandt alle varerne; derfor tilføjer vi 4 ved M[4][6] vist som nedenfor:

Når i = 4, er W = 7

Vægten svarende til værdien 4 er 6, dvs. w₄= 6. Da vi har fire genstande i sættet med vægte henholdsvis 3, 4, 5 og 6, og rygsækkens vægt er 7. Her, hvis vi tilføjer to emner med vægt 3 og 4, vil det give det maksimale profit, dvs. (2 + 3) er lig med 5, så vi tilføjer 5 ved M[4][7] vist som nedenfor:

Når i = 4, er W = 8

Vægten svarende til værdien 4 er 6, dvs. w₄= 6. Da vi har fire genstande i sættet med vægte henholdsvis 3, 4, 5 og 6, og rygsækkens vægt er 8. Her, hvis vi tilføjer to emner med vægt 3 og 4, vil det give det maksimale profit, dvs. (2 + 3) er lig med 5, så vi tilføjer 5 ved M[4][8] vist som nedenfor:

Som vi kan observere i ovenstående tabel, er 5 den maksimale fortjeneste blandt alle poster. Markøren peger på den sidste række og den sidste kolonne med værdien 5. Nu vil vi sammenligne værdien 5 med den forrige række; hvis den foregående række, dvs. i = 3, indeholder den samme værdi 5, vil markøren flytte sig opad. Da den forrige række indeholder værdien 5, vil markøren blive flyttet opad som vist i nedenstående tabel:

Igen vil vi sammenligne værdien 5 fra ovenstående række, dvs. i = 2. Da ovenstående række indeholder værdien 5, vil markøren igen blive flyttet opad som vist i nedenstående tabel:

Igen vil vi sammenligne værdien 5 fra ovenstående række, dvs. i = 1. Da ovenstående række ikke indeholder den samme værdi, så vil vi betragte rækken i=1, og vægten svarende til rækken er 4. Derfor , vi har valgt vægten 4, og vi har afvist vægtene 5 og 6 vist nedenfor:

x = { 1, 0, 0}

Fortjenesten svarende til vægten er 3. Derfor er den resterende fortjeneste (5 - 3) lig med 2. Nu vil vi sammenligne denne værdi 2 med rækken i = 2. Da rækken (i = 1) indeholder værdien 2 ; derfor flyttede markøren opad vist nedenfor:

Igen sammenligner vi værdien 2 med en ovenstående række, dvs. i = 1. Da rækken i =0 ikke indeholder værdien 2, vil række i = 1 blive valgt, og vægten svarende til i = 1 er vist 3 under:

X = {1, 1, 0, 0}

Fortjenesten svarende til vægten er 2. Derfor er den resterende fortjeneste 0. Vi sammenligner 0-værdien med ovenstående række. Da ovenstående række indeholder en 0-værdi, men fortjenesten svarende til denne række er 0. I denne opgave vælges to vægte, dvs. 3 og 4 for at maksimere fortjenesten.