Her er ryggsekken som en beholder eller en pose. Anta at vi har gitt noen gjenstander som har en viss vekt eller fortjeneste. Vi må legge noen gjenstander i ryggsekken på en slik måte at totalverdien gir maksimal fortjeneste.

For eksempel er vekten på beholderen 20 kg. Vi må velge varene på en slik måte at summen av vekten av gjenstandene enten skal være mindre enn eller lik vekten på beholderen, og fortjenesten skal være maksimal.

Det er to typer ryggsekkproblemer:

• 0/1 ryggsekkproblem
• Fraksjonert ryggsekkproblem

Vi vil diskutere begge problemene én etter én. Først vil vi lære om 0/1 ryggsekkproblemet.

Hva er 0/1 ryggsekkproblemet?

0/1 ryggsekkproblemet betyr at gjenstandene enten er helt eller ingen gjenstander er fylt i en ryggsekk. For eksempel har vi to varer som veier henholdsvis 2 kg og 3 kg. Hvis vi velger varen på 2 kg, kan vi ikke velge varen på 1 kg fra varen på 2 kg (varen er ikke delbar); vi må plukke varen på 2 kg helt. Dette er et 0/1 ryggsekkproblem der enten vi plukker varen helt eller så velger vi den. 0/1 ryggsekk-problemet løses av dynamisk programmering.

Hva er problemet med fraksjonert ryggsekk?

Fraksjonsryggsekkproblemet gjør at vi kan dele varen. For eksempel har vi en vare på 3 kg, så kan vi plukke varen på 2 kg og la varen på 1 kg stå. Problemet med fraksjonert ryggsekk løses av Greedy-tilnærmingen.

Eksempel på 0/1 ryggsekkproblem.

Tenk på at problemet med vekter og overskudd er:

Vekter: {3, 4, 6, 5}

Fortjeneste: {2, 3, 1, 4}

Vekten på ryggsekken er 8 kg

Antall varer er 4

Problemet ovenfor kan løses ved å bruke følgende metode:

x_Jeg= {1, 0, 0, 1}

= {0, 0, 0, 1}

les csv-filen i java

= {0, 1, 0, 1}

Ovennevnte er de mulige kombinasjonene. 1 betyr at varen er fullstendig plukket og 0 betyr at ingen vare er plukket. Siden det er 4 elementer, vil mulige kombinasjoner være:

2⁴= 16; Så. Det er 16 mulige kombinasjoner som kan lages ved å bruke problemet ovenfor. Når alle kombinasjonene er laget, må vi velge kombinasjonen som gir maksimal fortjeneste.

En annen tilnærming for å løse problemet er dynamisk programmering. I dynamisk programmering tilnærming er det kompliserte problemet delt inn i delproblemer, så finner vi løsningen på et delproblem og løsningen av delproblemet vil bli brukt til å finne løsningen på et komplekst problem.

Hvordan kan dette problemet løses ved å bruke tilnærmingen til dynamisk programmering?

Først,

vi lager en matrise vist som nedenfor:

I matrisen ovenfor representerer kolonnene vekten, det vil si 8. Radene representerer fortjenesten og vekten til varer. Her har vi ikke tatt vekten 8 direkte, problemet er delt inn i deloppgaver, dvs. 0, 1, 2, 3, 4, 5, 6, 7, 8. Løsningen av deloppgavene vil bli lagret i celler og svaret på problemet vil bli lagret i den siste cellen. Først skriver vi vektene i stigende rekkefølge og fortjeneste i henhold til vektene vist som nedenfor:

I_Jeg= {3, 4, 5, 6}

s_Jeg= {2, 3, 4, 1}

Den første raden og den første kolonnen vil være 0 da det ikke er noe element for w=0

Når i=1, W=1

I₁= 3; Siden vi bare har én gjenstand i settet med vekt 3, men ryggsekkens kapasitet er 1. Vi kan ikke fylle gjenstanden på 3 kg i ryggsekken med kapasitet 1 kg, så legg til 0 ved M[1][1] vist som nedenfor :

Når i = 1, er W = 2

I₁= 3; Siden vi bare har én gjenstand i settet med vekt 3, men ryggsekkens kapasitet er 2. Vi kan ikke fylle gjenstanden på 3 kg i ryggsekken med kapasitet 2 kg, så legg til 0 ved M[1][2] vist som nedenfor :

Når i=1, W=3

I₁= 3; Siden vi bare har ett element i settet som har vekt lik 3, og vekten på ryggsekken også er 3; derfor kan vi fylle ryggsekken med en vekt lik 3. Vi legger fortjeneste tilsvarende vekten 3, dvs. 2 ved M[1][3] vist som nedenfor:

Når i=1, W = 4

_W1= 3; Siden vi bare har ett element i settet som har vekt lik 3, og vekten på ryggsekken er 4; derfor kan vi fylle ryggsekken med en vekt lik 3. Vi legger fortjeneste tilsvarende vekten 3, dvs. 2 ved M[1][4] vist som nedenfor:

Når i=1, W = 5

_W1= 3; Siden vi bare har ett element i settet som har vekt lik 3, og vekten på ryggsekken er 5; derfor kan vi fylle ryggsekken med en vekt lik 3. Vi legger fortjeneste tilsvarende vekten 3, dvs. 2 ved M[1][5] vist som nedenfor:

Når i =1, W=6

_W1= 3; Siden vi bare har ett element i settet med vekt lik 3, og vekten på ryggsekken er 6; derfor kan vi fylle ryggsekken med en vekt lik 3. Vi legger fortjeneste tilsvarende vekten 3, dvs. 2 ved M[1][6] vist som nedenfor:

Når i=1, W = 7

_W1= 3; Siden vi bare har ett element i settet med vekt lik 3, og vekten på ryggsekken er 7; derfor kan vi fylle ryggsekken med en vekt lik 3. Vi legger fortjeneste tilsvarende vekten 3, dvs. 2 ved M[1][7] vist som nedenfor:

Når i =1, W =8

_W1= 3; Siden vi bare har ett element i settet med vekt lik 3, og vekten på ryggsekken er 8; derfor kan vi fylle ryggsekken med en vekt lik 3. Vi legger fortjeneste tilsvarende vekten 3, dvs. 2 ved M[1][8] vist som nedenfor:

Nå økes verdien av 'i' og blir 2.

Når i =2, er W = 1

Vekten som tilsvarer verdien 2 er 4, dvs. w₂= 4. Siden vi bare har én gjenstand i settet med vekt lik 4, og vekten på ryggsekken er 1. Vi kan ikke legge gjenstanden med vekt 4 i en ryggsekk, så vi legger til 0 ved M[2][1 ] vist som nedenfor:

Når i =2, er W = 2

Vekten som tilsvarer verdien 2 er 4, dvs. w₂= 4. Siden vi bare har én gjenstand i settet med vekt lik 4, og vekten på ryggsekken er 2. Vi kan ikke legge gjenstanden med vekt 4 i en ryggsekk, så vi legger til 0 ved M[2][2 ] vist som nedenfor:

Når i =2, er W = 3

Vekten som tilsvarer verdien 2 er 4, dvs. w₂= 4. Siden vi har to gjenstander i settet med vekt 3 og 4, og vekten på ryggsekken er 3. Vi kan legge gjenstanden med vekt 3 i en ryggsekk, så vi legger til 2 ved M[2][3] vist som nedenfor:

Når i =2, er W = 4

Vekten som tilsvarer verdien 2 er 4, dvs. w₂= 4. Siden vi har to gjenstander i settet med vekt 3 og 4, og vekten på ryggsekken er 4. Vi kan legge gjenstand med vekt 4 i en ryggsekk da fortjenesten tilsvarende vekt 4 er mer enn gjenstanden som har vekt 3, så vi legger til 3 ved M[2][4] vist som nedenfor:

Når i = 2, er W = 5

Vekten som tilsvarer verdien 2 er 4, dvs. w₂= 4. Siden vi har to gjenstander i settet med vekt 3 og 4, og vekten på ryggsekken er 5. Vi kan legge gjenstand med vekt 4 i en ryggsekk og fortjenesten tilsvarende vekt er 3, så legger vi til 3 kl. M[2][5] vist som nedenfor:

Når i = 2, er W = 6

Vekten som tilsvarer verdien 2 er 4, dvs. w₂= 4. Siden vi har to gjenstander i settet med vekt 3 og 4, og vekten på ryggsekken er 6. Vi kan legge gjenstand med vekt 4 i en ryggsekk og fortjenesten tilsvarende vekt er 3, så legger vi til 3 kl. M[2][6] vist som nedenfor:

Når i = 2, er W = 7

Vekten som tilsvarer verdien 2 er 4, dvs. w₂= 4. Siden vi har to gjenstander i settet med vekt 3 og 4, og vekten på ryggsekken er 7. Vi kan legge gjenstand med vekt 4 og 3 i en ryggsekk og fortjenesten som tilsvarer vekter er 2 og 3; derfor er den totale fortjenesten 5, så vi legger til 5 ved M[2][7] vist som nedenfor:

Når i = 2, er W = 8

Vekten som tilsvarer verdien 2 er 4, dvs. w₂= 4. Siden vi har to gjenstander i settet med vekt 3 og 4, og vekten på ryggsekken er 7. Vi kan legge gjenstand med vekt 4 og 3 i en ryggsekk og fortjenesten som tilsvarer vekter er 2 og 3; derfor er den totale fortjenesten 5, så vi legger til 5 ved M[2][7] vist som nedenfor:

Nå økes verdien av 'i' og blir 3.

Når i = 3, er W = 1

10 av 60

Vekten som tilsvarer verdien 3 er 5, dvs. w₃= 5. Siden vi har tre gjenstander i settet med vektene 3, 4 og 5, og vekten på ryggsekken er 1. Vi kan ikke legge noen av gjenstandene i en ryggsekk, så vi legger til 0 ved M[3][ 1] vist som nedenfor:

Når i = 3, er W = 2

Vekten som tilsvarer verdien 3 er 5, dvs. w₃= 5. Siden vi har tre gjenstander i settet med vekt 3, 4 og 5, og vekten på ryggsekken er 1. Vi kan ikke legge noen av gjenstandene i en ryggsekk, så vi legger til 0 ved M[3][ 2] vist som nedenfor:

Når i = 3, er W = 3

Vekten som tilsvarer verdien 3 er 5, dvs. w₃= 5. Siden vi har tre varer i settet med henholdsvis vekt 3, 4 og 5 og vekten på ryggsekken er 3. Gjenstanden med vekt 3 kan legges i ryggsekken og fortjenesten tilsvarende varen er 2, så vi legger til 2 ved M[3][3] vist som nedenfor:

Når i = 3, er W = 4

Vekten som tilsvarer verdien 3 er 5, dvs. w₃= 5. Siden vi har tre gjenstander i settet med vekt 3, 4 og 5, og vekten på ryggsekken er 4. Vi kan beholde gjenstanden med vekt 3 eller 4; fortjenesten (3) som tilsvarer vekten 4 er mer enn fortjenesten tilsvarende vekten 3, så vi legger til 3 ved M[3][4] vist som nedenfor:

Når i = 3, er W = 5

Vekten som tilsvarer verdien 3 er 5, dvs. w₃= 5. Siden vi har tre gjenstander i settet med henholdsvis vekt 3, 4 og 5, og vekten på ryggsekken er 5. Vi kan beholde gjenstanden med vekt 3, 4 eller 5; fortjenesten (3) som tilsvarer vekten 4 er mer enn fortjenesten tilsvarende vekten 3 og 5, så vi legger til 3 ved M[3][5] vist som nedenfor:

Når i =3, er W = 6

Vekten som tilsvarer verdien 3 er 5, dvs. w₃= 5. Siden vi har tre gjenstander i settet med henholdsvis vekt 3, 4 og 5, og vekten på ryggsekken er 6. Vi kan beholde gjenstanden med vekt 3, 4 eller 5; fortjenesten (3) som tilsvarer vekten 4 er mer enn fortjenesten tilsvarende vekten 3 og 5, så vi legger til 3 ved M[3][6] vist som nedenfor:

Når i =3, er W = 7

Vekten som tilsvarer verdien 3 er 5, dvs. w₃= 5. Siden vi har tre gjenstander i settet med henholdsvis vekt 3, 4 og 5, og vekten på ryggsekken er 7. I dette tilfellet kan vi beholde både gjenstandene med vekt 3 og 4, summen av overskuddet ville være lik (2 + 3), dvs. 5, så vi legger til 5 ved M[3][7] vist som nedenfor:

Når i = 3, er W = 8

Java eksempel programmer

Vekten som tilsvarer verdien 3 er 5, dvs. w₃= 5. Siden vi har tre gjenstander i settet med henholdsvis vekt 3, 4 og 5, og vekten på ryggsekken er 8. I dette tilfellet kan vi beholde både gjenstandene med vekt 3 og 4, summen av profitt vil være lik (2 + 3), dvs. 5, så vi legger til 5 ved M[3][8] vist som nedenfor:

Nå økes verdien av 'i' og blir 4.

Når i = 4, er W = 1

Vekten som tilsvarer verdien 4 er 6, dvs. w₄= 6. Siden vi har fire gjenstander i settet med vekter henholdsvis 3, 4, 5 og 6, og vekten på ryggsekken er 1. Vekten på alle gjenstandene er mer enn vekten på ryggsekken, så vi kan ikke legg til en gjenstand i ryggsekken; Derfor legger vi til 0 ved M[4][1] vist som nedenfor:

Når i = 4, er W = 2

Vekten som tilsvarer verdien 4 er 6, dvs. w₄= 6. Siden vi har fire gjenstander i settet med vekter henholdsvis 3, 4, 5 og 6, og vekten på ryggsekken er 2. Vekten på alle gjenstandene er mer enn vekten på ryggsekken, så vi kan ikke legg til en gjenstand i ryggsekken; Derfor legger vi til 0 ved M[4][2] vist som nedenfor:

Når i = 4, er W = 3

Vekten som tilsvarer verdien 4 er 6, dvs. w₄= 6. Siden vi har fire gjenstander i settet med vekt 3, 4, 5 og 6, og vekten på ryggsekken er 3. Gjenstanden med vekt 3 kan legges i ryggsekken og fortjenesten tilsvarer vekt 4 er 2, så vi legger til 2 ved M[4][3] vist som nedenfor:

Når i = 4, er W = 4

Vekten som tilsvarer verdien 4 er 6, dvs. w₄= 6. Siden vi har fire gjenstander i settet med vekt 3, 4, 5 og 6, og vekten på ryggsekken er 4. Gjenstanden med vekt 4 kan legges i ryggsekken og fortjenesten tilsvarer vekt 4 er 3, så vi legger til 3 ved M[4][4] vist som nedenfor:

Når i = 4, er W = 5

Vekten som tilsvarer verdien 4 er 6, dvs. w₄= 6. Siden vi har fire gjenstander i settet med vekt 3, 4, 5 og 6, og vekten på ryggsekken er 5. Gjenstanden med vekt 4 kan legges i ryggsekken og fortjenesten tilsvarer vekt 4 er 3, så vi legger til 3 ved M[4][5] vist som nedenfor:

Når i = 4, er W = 6

Vekten som tilsvarer verdien 4 er 6, dvs. w₄= 6. Siden vi har fire gjenstander i settet med vekter henholdsvis 3, 4, 5 og 6, og vekten på ryggsekken er 6. I dette tilfellet kan vi legge gjenstandene i ryggsekken enten med vekt 3, 4 , 5 eller 6 men fortjenesten, dvs. 4 som tilsvarer vekten 6 er høyest blant alle varene; derfor legger vi til 4 ved M[4][6] vist som nedenfor:

Når i = 4, er W = 7

Vekten som tilsvarer verdien 4 er 6, dvs. w₄= 6. Siden vi har fire elementer i settet med vekt 3, 4, 5 og 6, og vekten på ryggsekken er 7. Her, hvis vi legger til to elementer med vekt 3 og 4, vil den produsere maksimalt profitt, dvs. (2 + 3) er lik 5, så vi legger til 5 ved M[4][7] vist som nedenfor:

Når i = 4, er W = 8

Vekten som tilsvarer verdien 4 er 6, dvs. w₄= 6. Siden vi har fire elementer i settet med vekt 3, 4, 5 og 6, og vekten på ryggsekken er 8. Her, hvis vi legger til to elementer med vekt 3 og 4, vil den produsere maksimalt profitt, dvs. (2 + 3) er lik 5, så vi legger til 5 ved M[4][8] vist som nedenfor:

Som vi kan observere i tabellen ovenfor at 5 er maksimal fortjeneste blant alle oppføringene. Pekeren peker på den siste raden og den siste kolonnen har 5 verdi. Nå skal vi sammenligne 5-verdien med forrige rad; hvis forrige rad, dvs. i = 3 inneholder samme verdi 5, vil pekeren skifte oppover. Siden forrige rad inneholder verdien 5, vil pekeren flyttes oppover som vist i tabellen nedenfor:

Igjen vil vi sammenligne verdien 5 fra raden ovenfor, dvs. i = 2. Siden raden ovenfor inneholder verdien 5, vil pekeren igjen bli forskjøvet oppover som vist i tabellen nedenfor:

Igjen vil vi sammenligne verdien 5 fra raden ovenfor, dvs. i = 1. Siden raden ovenfor ikke inneholder samme verdi, vil vi vurdere raden i=1, og vekten som tilsvarer raden er 4. Derfor , vi har valgt vekt 4 og vi har avvist vektene 5 og 6 vist nedenfor:

x = { 1, 0, 0}

Fortjenesten som tilsvarer vekten er 3. Derfor er den resterende fortjenesten (5 - 3) lik 2. Nå skal vi sammenligne denne verdien 2 med raden i = 2. Siden raden (i = 1) inneholder verdien 2 ; derfor flyttet pekeren oppover vist nedenfor:

Igjen sammenligner vi verdien 2 med en over rad, dvs. i = 1. Siden raden i =0 ikke inneholder verdien 2, vil rad i = 1 bli valgt og vekten som tilsvarer i = 1 er 3 vist under:

X = {1, 1, 0, 0}

Fortjenesten som tilsvarer vekten er 2. Derfor er den resterende fortjenesten 0. Vi sammenligner 0-verdien med raden ovenfor. Siden ovennevnte rad inneholder en 0-verdi, men fortjenesten som tilsvarer denne raden er 0. I denne oppgaven velges to vekter, dvs. 3 og 4 for å maksimere fortjenesten.