Hier is de knapzak als een container of een tas. Stel dat we een aantal items hebben gegeven die een bepaald gewicht of winst hebben. We moeten sommige spullen zo in de rugzak stoppen dat de totale waarde een maximale winst oplevert.

Het gewicht van de container is bijvoorbeeld 20 kg. We moeten de artikelen zo selecteren dat de som van het gewicht van de artikelen kleiner of gelijk moet zijn aan het gewicht van de container, en de winst maximaal moet zijn.

Er zijn twee soorten knapzakproblemen:

• 0/1 knapzakprobleem
• Fractioneel knapzakprobleem

We zullen beide problemen één voor één bespreken. Eerst zullen we leren over het 0/1 knapzakprobleem.

Wat is het 0/1 knapzakprobleem?

Het 0/1 knapzakprobleem houdt in dat de spullen óf helemaal óf helemaal niet gevuld zijn in een knapzak. We hebben bijvoorbeeld twee artikelen met een gewicht van respectievelijk 2 kg en 3 kg. Als we het artikel van 2 kg kiezen, kunnen we niet het artikel van 1 kg van het artikel van 2 kg kiezen (artikel is niet deelbaar); we moeten het artikel van 2 kg volledig kiezen. Dit is een 0/1 knapzakprobleem waarbij we het item volledig kiezen of dat item kiezen. Het 0/1 knapzakprobleem wordt opgelost door dynamisch programmeren.

Wat is het fractionele knapzakprobleem?

Het fractionele knapzakprobleem betekent dat we het item kunnen verdelen. Hebben wij bijvoorbeeld een artikel van 3 kg, dan kunnen wij het artikel van 2 kg oppakken en het artikel van 1 kg laten staan. Het fractionele knapzakprobleem wordt opgelost door de Greedy-benadering.

Voorbeeld van een 0/1 knapzakprobleem.

Beschouw het probleem met gewichten en winsten als volgt:

Gewichten: {3, 4, 6, 5}

Winst: {2, 3, 1, 4}

Het gewicht van de knapzak bedraagt ​​8 kg

Het aantal artikelen bedraagt ​​4

Het bovenstaande probleem kan worden opgelost door de volgende methode te gebruiken:

X_i= {1, 0, 0, 1}

= {0, 0, 0, 1}

binaire boomtypen

= {0, 1, 0, 1}

Bovenstaande zijn de mogelijke combinaties. 1 geeft aan dat het artikel volledig is gepickt en 0 betekent dat er geen artikel is gepickt. Omdat er 4 items zijn, zijn de mogelijke combinaties:

2⁴= 16; Dus. Er zijn 16 mogelijke combinaties die gemaakt kunnen worden door gebruik te maken van het bovenstaande probleem. Zodra alle combinaties zijn gemaakt, moeten we de combinatie selecteren die de maximale winst oplevert.

Een andere benadering om het probleem op te lossen is de dynamische programmeerbenadering. Bij een dynamische programmeerbenadering wordt het gecompliceerde probleem opgedeeld in deelproblemen. Vervolgens vinden we de oplossing van een deelprobleem en de oplossing van het deelprobleem zal worden gebruikt om de oplossing van een complex probleem te vinden.

Hoe kan dit probleem worden opgelost door gebruik te maken van de dynamische programmeeraanpak?

Eerst,

we creëren een matrix zoals hieronder weergegeven:

In de bovenstaande matrix vertegenwoordigen de kolommen het gewicht, d.w.z. 8. De rijen vertegenwoordigen de winsten en het gewicht van items. Hier hebben we het gewicht 8 niet rechtstreeks genomen, het probleem is verdeeld in deelproblemen, d.w.z. 0, 1, 2, 3, 4, 5, 6, 7, 8. De oplossing van de deelproblemen zou worden opgeslagen in de cellen en het antwoord op het probleem zou in de laatste cel worden opgeslagen. Eerst schrijven we de gewichten in oplopende volgorde en de winsten volgens hun gewichten, zoals hieronder weergegeven:

In_i= {3, 4, 5, 6}

P_i= {2, 3, 4, 1}

De eerste rij en de eerste kolom zouden 0 zijn, omdat er geen item is voor w=0

Wanneer i=1, W=1

In₁= 3; Omdat we slechts één item in de set hebben met een gewicht van 3, maar de capaciteit van de knapzak 1 is. We kunnen het item van 3 kg niet vullen in de knapzak met een capaciteit van 1 kg, dus voeg 0 toe bij M[1][1], zoals hieronder weergegeven :

Wanneer ik = 1, W = 2

In₁= 3; Omdat we slechts één item in de set hebben met een gewicht van 3, maar de capaciteit van de knapzak 2 is. We kunnen het item van 3 kg niet vullen in de knapzak met een capaciteit van 2 kg, dus voeg 0 toe bij M[1][2], zoals hieronder weergegeven :

Wanneer i=1, W=3

In₁= 3; Omdat we slechts één item in de set hebben met een gewicht gelijk aan 3, en het gewicht van de knapzak ook 3 is; daarom kunnen we de knapzak vullen met een voorwerp met een gewicht gelijk aan 3. We zetten de winst die overeenkomt met het gewicht 3, dat wil zeggen 2, op M[1][3], zoals hieronder weergegeven:

Wanneer i=1, W=4

_W1= 3; Omdat we slechts één item in de set hebben met een gewicht gelijk aan 3, en het gewicht van de knapzak 4 is; daarom kunnen we de knapzak vullen met een voorwerp met een gewicht gelijk aan 3. We zetten de winst die overeenkomt met het gewicht 3, dat wil zeggen 2, op M[1][4], zoals hieronder weergegeven:

Wanneer i=1, W=5

_W1= 3; Omdat we slechts één item in de set hebben met een gewicht gelijk aan 3, en het gewicht van de knapzak 5; daarom kunnen we de knapzak vullen met een voorwerp met een gewicht gelijk aan 3. We zetten de winst die overeenkomt met het gewicht 3, dat wil zeggen 2, op M[1][5], zoals hieronder weergegeven:

Wanneer ik =1, W=6

_W1= 3; Omdat we slechts één item in de set hebben met een gewicht gelijk aan 3, en het gewicht van de knapzak 6; daarom kunnen we de knapzak vullen met een voorwerp met een gewicht gelijk aan 3. We zetten de winst die overeenkomt met het gewicht 3, dat wil zeggen 2, op M[1][6], zoals hieronder weergegeven:

Wanneer i=1, W=7

_W1= 3; Omdat we slechts één item in de set hebben met een gewicht gelijk aan 3, en het gewicht van de knapzak 7; daarom kunnen we de knapzak vullen met een voorwerp met een gewicht gelijk aan 3. We zetten de winst die overeenkomt met het gewicht 3, dat wil zeggen 2, op M[1][7], zoals hieronder weergegeven:

Wanneer ik =1, W =8

_W1= 3; Omdat we slechts één item in de set hebben met een gewicht gelijk aan 3, en het gewicht van de knapzak 8; daarom kunnen we de knapzak vullen met een voorwerp met een gewicht gelijk aan 3. We zetten de winst die overeenkomt met het gewicht 3, dat wil zeggen 2, op M[1][8], zoals hieronder weergegeven:

Nu wordt de waarde van 'i' verhoogd en wordt 2.

Wanneer ik = 2, W = 1

Het gewicht dat overeenkomt met de waarde 2 is 4, d.w.z. w₂= 4. Omdat we maar één item in de set hebben met een gewicht gelijk aan 4, en het gewicht van de knapzak 1 is. We kunnen het item met gewicht 4 niet in een knapzak stoppen, dus tellen we 0 op bij M[2][1 ] zoals hieronder weergegeven:

Wanneer ik = 2, W = 2

Het gewicht dat overeenkomt met de waarde 2 is 4, d.w.z. w₂= 4. Omdat we maar één item in de set hebben met een gewicht gelijk aan 4, en het gewicht van de knapzak 2 is. We kunnen het item met gewicht 4 niet in een knapzak stoppen, dus tellen we 0 op bij M[2][2 ] zoals hieronder weergegeven:

Wanneer ik = 2, W = 3

Het gewicht dat overeenkomt met de waarde 2 is 4, d.w.z. w₂= 4. Omdat we twee items in de set hebben met gewichten 3 en 4, en het gewicht van de knapzak 3 is. We kunnen het item met gewicht 3 in een knapzak stoppen, dus tellen we 2 op bij M[2][3] weergegeven zoals hieronder:

Wanneer ik = 2, W = 4

Het gewicht dat overeenkomt met de waarde 2 is 4, d.w.z. w₂= 4. Omdat we twee items in de set hebben met de gewichten 3 en 4, en het gewicht van de knapzak 4 is, kunnen we het item met gewicht 4 in een knapzak stoppen, omdat de winst die overeenkomt met gewicht 4 meer is dan het item met gewicht 3, dus we voegen 3 toe bij M[2][4], zoals hieronder weergegeven:

Wanneer ik = 2, W = 5

Het gewicht dat overeenkomt met de waarde 2 is 4, d.w.z. w₂= 4. Omdat we twee items in de set hebben met de gewichten 3 en 4, en het gewicht van de knapzak 5 is. We kunnen het item met gewicht 4 in een knapzak stoppen en de winst die overeenkomt met het gewicht is 3, dus tellen we 3 op bij M[2][5] weergegeven zoals hieronder:

Wanneer ik = 2, W = 6

Het gewicht dat overeenkomt met de waarde 2 is 4, d.w.z. w₂= 4. Omdat we twee items in de set hebben met de gewichten 3 en 4, en het gewicht van de knapzak 6 is. We kunnen het item met gewicht 4 in een knapzak stoppen en de winst die overeenkomt met het gewicht is 3, dus tellen we 3 op bij M[2][6] weergegeven zoals hieronder:

Wanneer ik = 2, W = 7

Het gewicht dat overeenkomt met de waarde 2 is 4, d.w.z. w₂= 4. Omdat we twee items in de set hebben met de gewichten 3 en 4, en het gewicht van de knapzak 7 is. We kunnen het item met het gewicht 4 en 3 in een knapzak stoppen en de winst die overeenkomt met de gewichten is 2 en 3; daarom is de totale winst 5, dus voegen we 5 toe bij M[2][7], zoals hieronder weergegeven:

Wanneer ik = 2, W = 8

Het gewicht dat overeenkomt met de waarde 2 is 4, d.w.z. w₂= 4. Omdat we twee items in de set hebben met de gewichten 3 en 4, en het gewicht van de knapzak 7 is. We kunnen het item met het gewicht 4 en 3 in een knapzak stoppen en de winst die overeenkomt met de gewichten is 2 en 3; daarom is de totale winst 5, dus voegen we 5 toe bij M[2][7], zoals hieronder weergegeven:

Nu wordt de waarde van 'i' verhoogd en wordt 3.

Wanneer ik = 3, W = 1

hoekig materiaal

Het gewicht dat overeenkomt met de waarde 3 is 5, d.w.z. w₃= 5. Omdat we drie items in de set hebben met de gewichten 3, 4 en 5, en het gewicht van de knapzak 1 is. We kunnen geen van beide items in een knapzak stoppen, dus tellen we 0 op bij M[3][ 1] zoals hieronder weergegeven:

Wanneer ik = 3, W = 2

Het gewicht dat overeenkomt met de waarde 3 is 5, d.w.z. w₃= 5. Omdat we drie items in de set hebben met een gewicht van 3, 4 en 5, en het gewicht van de knapzak 1 is. We kunnen geen van beide items in een knapzak stoppen, dus tellen we 0 op bij M[3][ 2] zoals hieronder weergegeven:

Wanneer ik = 3, W = 3

Het gewicht dat overeenkomt met de waarde 3 is 5, d.w.z. w₃= 5. Omdat we drie items in de set hebben met respectievelijk gewicht 3, 4 en 5 en het gewicht van de knapzak 3 is. Het item met een gewicht van 3 kan in de knapzak worden gedaan en de winst die overeenkomt met het item is 2, dus voegen we 2 toe bij M[3][3], zoals hieronder weergegeven:

Wanneer ik = 3, W = 4

Het gewicht dat overeenkomt met de waarde 3 is 5, d.w.z. w₃= 5. Omdat we drie items in de set hebben met respectievelijk gewicht 3, 4 en 5, en het gewicht van de knapzak 4 is, kunnen we het item met gewicht 3 of 4 behouden; de winst (3) die overeenkomt met gewicht 4 is meer dan de winst die overeenkomt met gewicht 3, dus voegen we 3 toe bij M[3][4], zoals hieronder weergegeven:

Wanneer ik = 3, W = 5

Het gewicht dat overeenkomt met de waarde 3 is 5, d.w.z. w₃= 5. Omdat we drie items in de set hebben met respectievelijk gewicht 3, 4 en 5, en het gewicht van de knapzak 5 is, kunnen we het item met gewicht 3, 4 of 5 behouden; de winst (3) die overeenkomt met het gewicht 4 is meer dan de winst die overeenkomt met het gewicht 3 en 5, dus voegen we 3 toe bij M[3][5], zoals hieronder weergegeven:

Wanneer ik =3, W = 6

Het gewicht dat overeenkomt met de waarde 3 is 5, d.w.z. w₃= 5. Omdat we drie items in de set hebben met respectievelijk gewicht 3, 4 en 5, en het gewicht van de knapzak 6 is, kunnen we het item met gewicht 3, 4 of 5 behouden; de winst (3) die overeenkomt met het gewicht 4 is meer dan de winst die overeenkomt met het gewicht 3 en 5, dus voegen we 3 toe bij M[3][6], zoals hieronder weergegeven:

Wanneer ik = 3, W = 7

Het gewicht dat overeenkomt met de waarde 3 is 5, d.w.z. w₃= 5. Omdat we drie items hebben in de set met respectievelijk gewicht 3, 4 en 5, en het gewicht van de knapzak 7 is. In dit geval kunnen we zowel de items met gewicht 3 als 4 behouden, de som van de winst zou gelijk zijn aan (2 + 3), dat wil zeggen 5, dus voegen we 5 toe bij M[3][7], zoals hieronder weergegeven:

Wanneer ik = 3, W = 8

fabrieksontwerppatroon

Het gewicht dat overeenkomt met de waarde 3 is 5, d.w.z. w₃= 5. Omdat we drie items hebben in de set met respectievelijk gewicht 3, 4 en 5, en het gewicht van de knapzak 8 is. In dit geval kunnen we zowel de items met gewicht 3 als 4 behouden, de som van de de winst zou gelijk zijn aan (2 + 3), dat wil zeggen 5, dus voegen we 5 toe bij M[3][8], zoals hieronder weergegeven:

Nu wordt de waarde van 'i' verhoogd en wordt 4.

Wanneer ik = 4, W = 1

Het gewicht dat overeenkomt met de waarde 4 is 6, d.w.z. w₄= 6. Omdat we vier items hebben in de reeks gewichten 3, 4, 5 en 6 respectievelijk, en het gewicht van de knapzak 1 is. Het gewicht van alle items is meer dan het gewicht van de knapzak, dus we kunnen niet voeg een item toe aan de knapzak; Daarom voegen we 0 toe bij M[4][1], zoals hieronder weergegeven:

Wanneer ik = 4, W = 2

Het gewicht dat overeenkomt met de waarde 4 is 6, d.w.z. w₄= 6. Omdat we vier items hebben in de reeks gewichten 3, 4, 5 en 6 respectievelijk, en het gewicht van de knapzak 2 is. Het gewicht van alle items is meer dan het gewicht van de knapzak, dus we kunnen dit niet doen voeg een item toe aan de knapzak; Daarom voegen we 0 toe bij M[4][2], zoals hieronder weergegeven:

Wanneer ik = 4, W = 3

Het gewicht dat overeenkomt met de waarde 4 is 6, d.w.z. w₄= 6. Omdat we vier items hebben in de set met respectievelijk de gewichten 3, 4, 5 en 6, en het gewicht van de knapzak 3 is. Het item met een gewicht van 3 kan in de knapzak worden gedaan en de winst komt overeen met de gewicht 4 is 2, dus we voegen 2 toe bij M[4][3], zoals hieronder weergegeven:

Wanneer ik = 4, W = 4

Het gewicht dat overeenkomt met de waarde 4 is 6, d.w.z. w₄= 6. Omdat we vier items hebben in de set met respectievelijk de gewichten 3, 4, 5 en 6, en het gewicht van de knapzak 4 is. Het item met een gewicht van 4 kan in de knapzak worden gedaan en de winst komt overeen met de gewicht 4 is 3, dus we voegen er 3 toe bij M[4][4], zoals hieronder weergegeven:

Wanneer ik = 4, W = 5

Het gewicht dat overeenkomt met de waarde 4 is 6, d.w.z. w₄= 6. Omdat we vier items hebben in de set met respectievelijk de gewichten 3, 4, 5 en 6, en het gewicht van de knapzak 5 is. Het item met een gewicht van 4 kan in de knapzak worden gedaan en de winst komt overeen met de gewicht 4 is 3, dus we voegen er 3 toe bij M[4][5], zoals hieronder weergegeven:

Wanneer ik = 4, W = 6

Het gewicht dat overeenkomt met de waarde 4 is 6, d.w.z. w₄= 6. Omdat we vier items hebben in de set met respectievelijk de gewichten 3, 4, 5 en 6, en het gewicht van de knapzak 6 is. In dit geval kunnen we de items in de knapzak plaatsen met een gewicht van respectievelijk 3, 4 , 5 of 6, maar de winst, d.w.z. 4 die overeenkomt met het gewicht 6, is het hoogst van alle items; daarom voegen we 4 toe bij M[4][6], zoals hieronder weergegeven:

Wanneer ik = 4, W = 7

Het gewicht dat overeenkomt met de waarde 4 is 6, d.w.z. w₄= 6. Omdat we vier items hebben in de reeks gewichten 3, 4, 5 en 6, en het gewicht van de knapzak 7 is. Als we hier twee items met gewichten 3 en 4 optellen, levert dit het maximale resultaat op winst, d.w.z. (2 + 3) is gelijk aan 5, dus we voegen 5 toe bij M[4][7], zoals hieronder weergegeven:

Wanneer ik = 4, W = 8

Het gewicht dat overeenkomt met de waarde 4 is 6, d.w.z. w₄= 6. Omdat we vier items hebben in de reeks gewichten 3, 4, 5 en 6, en het gewicht van de knapzak 8 is. Als we hier twee items met gewichten 3 en 4 optellen, levert dit het maximale resultaat op winst, d.w.z. (2 + 3) is gelijk aan 5, dus we voegen 5 toe bij M[4][8], zoals hieronder weergegeven:

Zoals we in de bovenstaande tabel kunnen zien, is 5 de maximale winst onder alle inzendingen. De aanwijzer wijst naar de laatste rij en de laatste kolom met een waarde van 5. Nu zullen we de waarde 5 vergelijken met de vorige rij; als de vorige rij, d.w.z. i = 3 dezelfde waarde 5 bevat, verschuift de wijzer naar boven. Omdat de vorige rij de waarde 5 bevat, wordt de aanwijzer naar boven verschoven, zoals weergegeven in de onderstaande tabel:

Opnieuw vergelijken we de waarde 5 uit de bovenstaande rij, d.w.z. i = 2. Omdat de bovenstaande rij de waarde 5 bevat, wordt de aanwijzer opnieuw naar boven verschoven, zoals weergegeven in de onderstaande tabel:

Opnieuw vergelijken we de waarde 5 uit de bovenstaande rij, d.w.z. i = 1. Omdat de bovenstaande rij niet dezelfde waarde bevat, beschouwen we de rij i=1, en het gewicht dat overeenkomt met de rij is 4. Daarom , hebben we het gewicht 4 geselecteerd en hebben we de hieronder weergegeven gewichten 5 en 6 afgewezen:

x = { 1, 0, 0}

De winst die overeenkomt met het gewicht is 3. Daarom is de resterende winst (5 - 3) gelijk aan 2. Nu zullen we deze waarde 2 vergelijken met de rij i = 2. Omdat de rij (i = 1) de waarde 2 bevat ; daarom verschoof de wijzer naar boven, zoals hieronder weergegeven:

Opnieuw vergelijken we de waarde 2 met een rij hierboven, d.w.z. i = 1. Omdat de rij i = 0 niet de waarde 2 bevat, wordt rij i = 1 geselecteerd en wordt het gewicht dat overeenkomt met de i = 1 3 weergegeven. onderstaand:

X = {1, 1, 0, 0}

De winst die overeenkomt met het gewicht is 2. Daarom is de resterende winst 0. We vergelijken de waarde 0 met de bovenstaande rij. Omdat de bovenstaande rij een 0-waarde bevat, maar de winst die overeenkomt met deze rij 0 is. In dit probleem worden twee gewichten geselecteerd, namelijk 3 en 4, om de winst te maximaliseren.