Aquí la motxilla és com un recipient o una bossa. Suposem que hem donat alguns articles que tenen alguns pesos o beneficis. Hem de posar alguns articles a la motxilla de manera que el valor total produeixi un benefici màxim.
Per exemple, el pes del contenidor és de 20 kg. Hem de seleccionar els articles de manera que la suma del pes dels articles sigui menor o igual al pes del contenidor i el benefici ha de ser màxim.
Hi ha dos tipus de problemes de motxilla:
- 0/1 problema de la motxilla
- Problema de la motxilla fraccionada
Debatrem els dos problemes un per un. Primer, coneixerem el problema de la motxilla 0/1.
Quin és el problema de la motxilla 0/1?
El problema de la motxilla 0/1 significa que els articles estan completament o no s'omplen cap element a la motxilla. Per exemple, tenim dos articles que pesen 2 kg i 3 kg, respectivament. Si escollim l'article de 2 kg, no podem triar l'article d'1 kg de l'article de 2 kg (l'article no és divisible); hem de triar completament l'article de 2 kg. Aquest és un problema de motxilla 0/1 en el qual o triem l'article completament o l'escollirem. El problema de la motxilla 0/1 es resol amb la programació dinàmica.
Quin és el problema de la motxilla fraccionada?
El problema de la motxilla fraccionada significa que podem dividir l'article. Per exemple, tenim un article de 3 kg, llavors podem escollir l'article de 2 kg i deixar l'article d'1 kg. El problema de la motxilla fraccionada es resol amb l'enfocament Greedy.
Exemple de problema de motxilla 0/1.
Considereu el problema amb pesos i beneficis:
Peses: {3, 4, 6, 5}
Beneficis: {2, 3, 1, 4}
El pes de la motxilla és de 8 kg
El nombre d'elements és 4
El problema anterior es pot resoldre mitjançant el mètode següent:
xi= {1, 0, 0, 1}
= {0, 0, 0, 1}
mysql canvia el tipus de columna
= {0, 1, 0, 1}
Les anteriors són les combinacions possibles. 1 indica que l'element està completament seleccionat i 0 significa que no s'ha seleccionat cap element. Com que hi ha 4 elements, les combinacions possibles seran:
24= 16; Tan. Hi ha 16 combinacions possibles que es poden fer utilitzant el problema anterior. Un cop fetes totes les combinacions, hem de seleccionar la combinació que proporcioni el màxim benefici.
Un altre enfocament per resoldre el problema és l'enfocament de programació dinàmica. En l'enfocament de programació dinàmica, el problema complicat es divideix en subproblemes, després trobem la solució d'un subproblema i la solució del subproblema s'utilitzarà per trobar la solució d'un problema complex.
Com es pot resoldre aquest problema utilitzant l'enfocament de programació dinàmica?
Primer,
creem una matriu que es mostra a continuació:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
| 0 | |||||||||
| 1 | |||||||||
| 2 | |||||||||
| 3 | |||||||||
| 4 |
A la matriu anterior, les columnes representen el pes, és a dir, 8. Les files representen els beneficis i els pesos dels articles. Aquí no hem pres el pes 8 directament, el problema es divideix en subproblemes, és a dir, 0, 1, 2, 3, 4, 5, 6, 7, 8. La solució dels subproblemes es guardaria en el cel·les i la resposta al problema s'emmagatzemarien a la cel·la final. Primer, escrivim els pesos en ordre ascendent i els beneficis segons els seus pesos que es mostren a continuació:
Eni= {3, 4, 5, 6}
pàgi= {2, 3, 4, 1}
La primera fila i la primera columna serien 0 ja que no hi ha cap element per a w=0
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | ||||||||
| 2 | 0 | ||||||||
| 3 | 0 | ||||||||
| 4 | 0 |
Quan i=1, W=1
En1= 3; Com que només tenim un article al conjunt que té un pes 3, però la capacitat de la motxilla és 1. No podem omplir l'article de 3 kg a la motxilla amb una capacitat d'1 kg, així que afegiu 0 a M[1][1] que es mostra a continuació. :
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | |||||||
| 2 | 0 | ||||||||
| 3 | 0 | ||||||||
| 4 | 0 |
Quan i = 1, W = 2
En1= 3; Com que només tenim un article al conjunt que té un pes 3, però la capacitat de la motxilla és de 2. No podem omplir l'article de 3 kg a la motxilla amb una capacitat de 2 kg, així que afegiu 0 a M[1][2] que es mostra a continuació. :
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | ||||||
| 2 | 0 | ||||||||
| 3 | 0 | ||||||||
| 4 | 0 |
Quan i=1, W=3
En1= 3; Com que només tenim un article al conjunt que té un pes igual a 3, i el pes de la motxilla també és 3; per tant, podem omplir la motxilla amb un article de pes igual a 3. Posem el benefici corresponent al pes 3, és a dir, 2 a M[1][3] que es mostra a continuació:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 2 | |||||
| 2 | 0 | ||||||||
| 3 | 0 | ||||||||
| 4 | 0 |
Quan i=1, W = 4
W1= 3; Com que només tenim un article al conjunt que té un pes igual a 3 i el pes de la motxilla és 4; per tant, podem omplir la motxilla amb un article de pes igual a 3. Posem el benefici corresponent al pes 3, és a dir, 2 a M[1][4] que es mostra a continuació:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 2 | 2 | ||||
| 2 | 0 | ||||||||
| 3 | 0 | ||||||||
| 4 | 0 |
Quan i = 1, W = 5
W1= 3; Com que només tenim un article al conjunt que té un pes igual a 3 i el pes de la motxilla és 5; per tant, podem omplir la motxilla amb un article de pes igual a 3. Posem el benefici corresponent al pes 3, és a dir, 2 a M[1][5] que es mostra a continuació:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 2 | 2 | 2 | |||
| 2 | 0 | ||||||||
| 3 | 0 | ||||||||
| 4 | 0 |
Quan i = 1, W = 6
W1= 3; Com que només tenim un article al conjunt que té un pes igual a 3 i el pes de la motxilla és 6; per tant, podem omplir la motxilla amb un article de pes igual a 3. Posem el benefici corresponent al pes 3, és a dir, 2 a M[1][6] que es mostra a continuació:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 2 | 2 | 2 | 2 | ||
| 2 | 0 | ||||||||
| 3 | 0 | ||||||||
| 4 | 0 |
Quan i = 1, W = 7
W1= 3; Com que només tenim un article al conjunt que té un pes igual a 3 i el pes de la motxilla és 7; per tant, podem omplir la motxilla amb un article de pes igual a 3. Posem el benefici corresponent al pes 3, és a dir, 2 a M[1][7] que es mostra a continuació:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 2 | 2 | 2 | 2 | 2 | |
| 2 | 0 | ||||||||
| 3 | 0 | ||||||||
| 4 | 0 |
Quan i = 1, W = 8
W1= 3; Com que només tenim un article al conjunt que té un pes igual a 3 i el pes de la motxilla és 8; per tant, podem omplir la motxilla amb un article de pes igual a 3. Posem el benefici corresponent al pes 3, és a dir, 2 a M[1][8] que es mostra a continuació:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 2 | 2 | 2 | 2 | 2 | 2 |
| 2 | 0 | ||||||||
| 3 | 0 | ||||||||
| 4 | 0 |
Ara el valor de 'i' s'incrementa i es converteix en 2.
Quan i = 2, W = 1
El pes corresponent al valor 2 és 4, és a dir, w2= 4. Com que només tenim un article del conjunt que té un pes igual a 4, i el pes de la motxilla és 1. No podem posar l'article de pes 4 a una motxilla, així que sumem 0 a M[2][1 ] que es mostra a continuació:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 2 | 2 | 2 | 2 | 2 | 2 |
| 2 | 0 | 0 | |||||||
| 3 | 0 | ||||||||
| 4 | 0 |
Quan i = 2, W = 2
El pes corresponent al valor 2 és 4, és a dir, w2= 4. Com que només tenim un article del conjunt que té un pes igual a 4, i el pes de la motxilla és 2. No podem posar l'article de pes 4 a una motxilla, així que sumem 0 a M[2][2 ] que es mostra a continuació:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 2 | 2 | 2 | 2 | 2 | 2 |
| 2 | 0 | 0 | 0 | ||||||
| 3 | 0 | ||||||||
| 4 | 0 |
Quan i = 2, W = 3
El pes corresponent al valor 2 és 4, és a dir, w2= 4. Com que tenim dos articles al conjunt que tenen pesos 3 i 4, i el pes de la motxilla és 3. Podem posar l'article de pes 3 en una motxilla, així que sumem 2 a M[2][3] es mostra a continuació:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 2 | 2 | 2 | 2 | 2 | 2 |
| 2 | 0 | 0 | 0 | 2 | |||||
| 3 | 0 | ||||||||
| 4 | 0 |
Quan i = 2, W = 4
El pes corresponent al valor 2 és 4, és a dir, w2= 4. Com que tenim dos articles al conjunt que tenen pes 3 i 4, i el pes de la motxilla és 4. Podem posar l'article de pes 4 en una motxilla ja que el benefici corresponent al pes 4 és més que l'article que té pes 3, així que afegim 3 a M[2][4] que es mostra a continuació:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 2 | 2 | 2 | 2 | 2 | 2 |
| 2 | 0 | 0 | 0 | 2 | 3 | ||||
| 3 | 0 | ||||||||
| 4 | 0 |
Quan i = 2, W = 5
El pes corresponent al valor 2 és 4, és a dir, w2= 4. Com que tenim dos articles al conjunt que tenen els pesos 3 i 4, i el pes de la motxilla és 5. Podem posar l'article de pes 4 en una motxilla i el benefici corresponent al pes és 3, així que sumem 3 a M[2][5] es mostra a continuació:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 2 | 2 | 2 | 2 | 2 | 2 |
| 2 | 0 | 0 | 0 | 2 | 3 | 3 | |||
| 3 | 0 | ||||||||
| 4 | 0 |
Quan i = 2, W = 6
El pes corresponent al valor 2 és 4, és a dir, w2= 4. Com que tenim dos articles al conjunt que tenen pesos 3 i 4, i el pes de la motxilla és 6. Podem posar l'article de pes 4 en una motxilla i el benefici corresponent al pes és 3, així que sumem 3 a M[2][6] es mostra a continuació:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 2 | 2 | 2 | 2 | 2 | 2 |
| 2 | 0 | 0 | 0 | 2 | 3 | 3 | 3 | ||
| 3 | 0 | ||||||||
| 4 | 0 |
Quan i = 2, W = 7
El pes corresponent al valor 2 és 4, és a dir, w2= 4. Com que tenim dos articles al conjunt que tenen pesos 3 i 4, i el pes de la motxilla és 7. Podem posar l'article de pes 4 i 3 en una motxilla i els beneficis corresponents als pesos són 2 i 3; per tant, el benefici total és 5, de manera que sumem 5 a M[2][7] que es mostra a continuació:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 2 | 2 | 2 | 2 | 2 | 2 |
| 2 | 0 | 0 | 0 | 0 | 3 | 3 | 3 | 5 | |
| 3 | 0 | ||||||||
| 4 | 0 |
Quan i = 2, W = 8
El pes corresponent al valor 2 és 4, és a dir, w2= 4. Com que tenim dos articles al conjunt que tenen pesos 3 i 4, i el pes de la motxilla és 7. Podem posar l'article de pes 4 i 3 en una motxilla i els beneficis corresponents als pesos són 2 i 3; per tant, el benefici total és 5, de manera que sumem 5 a M[2][7] que es mostra a continuació:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 2 | 2 | 2 | 2 | 2 | 2 |
| 2 | 0 | 0 | 0 | 2 | 3 | 3 | 3 | 5 | 5 |
| 3 | 0 | ||||||||
| 4 | 0 |
Ara el valor de 'i' s'incrementa i es converteix en 3.
Quan i = 3, W = 1
trencar java
El pes corresponent al valor 3 és 5, és a dir, w3= 5. Com que tenim tres articles en el conjunt que tenen pesos 3, 4 i 5, i el pes de la motxilla és 1. No podem posar cap dels elements en una motxilla, així que sumem 0 a M[3][ 1] es mostra a continuació:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 2 | 2 | 2 | 2 | 2 | 2 |
| 2 | 0 | 0 | 0 | 2 | 3 | 3 | 3 | 5 | 5 |
| 3 | 0 | 0 | |||||||
| 4 | 0 |
Quan i = 3, W = 2
El pes corresponent al valor 3 és 5, és a dir, w3= 5. Com que tenim tres articles al conjunt que tenen el pes 3, 4 i 5, i el pes de la motxilla és 1. No podem posar cap dels elements en una motxilla, així que sumem 0 a M[3][ 2] es mostra a continuació:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 2 | 2 | 2 | 2 | 2 | 2 |
| 2 | 0 | 0 | 0 | 2 | 3 | 3 | 3 | 5 | 5 |
| 3 | 0 | 0 | 0 | ||||||
| 4 | 0 |
Quan i = 3, W = 3
El pes corresponent al valor 3 és 5, és a dir, w3= 5. Com que tenim tres articles al conjunt de pes 3, 4 i 5 respectivament i el pes de la motxilla és 3. L'article amb un pes 3 es pot posar a la motxilla i el benefici corresponent a l'article és 2, així que afegim 2 a M[3][3] que es mostra a continuació:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 2 | 2 | 2 | 2 | 2 | 2 |
| 2 | 0 | 0 | 0 | 2 | 3 | 3 | 3 | 5 | 5 |
| 3 | 0 | 0 | 0 | 2 | |||||
| 4 | 0 |
Quan i = 3, W = 4
El pes corresponent al valor 3 és 5, és a dir, w3= 5. Com que tenim tres articles al conjunt de pes 3, 4 i 5 respectivament, i el pes de la motxilla és 4. Podem mantenir l'article de pes 3 o 4; el benefici (3) corresponent al pes 4 és més que el benefici corresponent al pes 3, de manera que sumem 3 a M[3][4] que es mostra a continuació:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 2 | 2 | 2 | 2 | 2 | 2 |
| 2 | 0 | 0 | 0 | 2 | 3 | 3 | 3 | 5 | 5 |
| 3 | 0 | 0 | 0 | 1 | 3 | ||||
| 4 | 0 |
Quan i = 3, W = 5
El pes corresponent al valor 3 és 5, és a dir, w3= 5. Com que tenim tres articles al conjunt de pes 3, 4 i 5 respectivament, i el pes de la motxilla és 5. Podem mantenir l'article de pes 3, 4 o 5; el benefici (3) corresponent al pes 4 és més que els beneficis corresponents al pes 3 i 5, de manera que sumem 3 a M[3][5] que es mostra a continuació:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 2 | 2 | 2 | 2 | 2 | 2 |
| 2 | 0 | 0 | 0 | 2 | 3 | 3 | 3 | 5 | 5 |
| 3 | 0 | 0 | 0 | 1 | 3 | 3 | |||
| 4 | 0 |
Quan i = 3, W = 6
El pes corresponent al valor 3 és 5, és a dir, w3= 5. Com que tenim tres articles en el conjunt de pes 3, 4 i 5 respectivament, i el pes de la motxilla és 6. Podem mantenir l'article de pes 3, 4 o 5; el benefici (3) corresponent al pes 4 és més que els beneficis corresponents al pes 3 i 5, de manera que sumem 3 a M[3][6] que es mostra a continuació:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 2 | 2 | 2 | 2 | 2 | 2 |
| 2 | 0 | 0 | 0 | 2 | 3 | 3 | 3 | 5 | 5 |
| 3 | 0 | 0 | 0 | 1 | 3 | 3 | 3 | ||
| 4 | 0 |
Quan i = 3, W = 7
El pes corresponent al valor 3 és 5, és a dir, w3= 5. Com que tenim tres articles en el conjunt de pes 3, 4 i 5 respectivament, i el pes de la motxilla és 7. En aquest cas, podem mantenir tant els articles de pes 3 com 4, la suma del benefici. seria igual a (2 + 3), és a dir, 5, de manera que sumem 5 a M[3][7] que es mostra a continuació:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 2 | 2 | 2 | 2 | 2 | 2 |
| 2 | 0 | 0 | 0 | 2 | 3 | 3 | 3 | 5 | 5 |
| 3 | 0 | 0 | 0 | 1 | 3 | 3 | 3 | 5 | |
| 4 | 0 |
Quan i = 3, W = 8
El pes corresponent al valor 3 és 5, és a dir, w3= 5. Com que tenim tres articles en el conjunt de pes 3, 4 i 5 respectivament, i el pes de la motxilla és 8. En aquest cas, podem conservar tant els elements de pes 3 com 4, la suma dels el benefici seria igual a (2 + 3), és a dir, 5, de manera que sumem 5 a M[3][8] que es mostra a continuació:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 2 | 2 | 2 | 2 | 2 | 2 |
| 2 | 0 | 0 | 0 | 2 | 3 | 3 | 3 | 5 | 5 |
| 3 | 0 | 0 | 0 | 1 | 3 | 3 | 3 | 5 | 5 |
| 4 | 0 |
Ara el valor de 'i' s'incrementa i es converteix en 4.
Quan i = 4, W = 1
El pes corresponent al valor 4 és 6, és a dir, w4= 6. Com que tenim quatre articles al conjunt de pesos 3, 4, 5 i 6 respectivament, i el pes de la motxilla és 1. El pes de tots els articles és més que el pes de la motxilla, per tant no podem afegir qualsevol element a la motxilla; Per tant, afegim 0 a M[4][1] que es mostra a continuació:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 2 | 2 | 2 | 2 | 2 | 2 |
| 2 | 0 | 0 | 0 | 2 | 3 | 3 | 3 | 5 | 5 |
| 3 | 0 | 0 | 0 | 1 | 3 | 3 | 3 | 5 | 5 |
| 4 | 0 | 0 |
Quan i = 4, W = 2
El pes corresponent al valor 4 és 6, és a dir, w4= 6. Com que tenim quatre articles al conjunt de pesos 3, 4, 5 i 6 respectivament, i el pes de la motxilla és 2. El pes de tots els articles és més que el pes de la motxilla, per tant no podem afegir qualsevol element a la motxilla; Per tant, afegim 0 a M[4][2] que es mostra a continuació:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 2 | 2 | 2 | 2 | 2 | 2 |
| 2 | 0 | 0 | 0 | 2 | 3 | 3 | 3 | 5 | 5 |
| 3 | 0 | 0 | 0 | 1 | 3 | 3 | 3 | 5 | 5 |
| 4 | 0 | 0 | 0 |
Quan i = 4, W = 3
El pes corresponent al valor 4 és 6, és a dir, w4= 6. Com que tenim quatre articles al conjunt de pesos 3, 4, 5 i 6 respectivament, i el pes de la motxilla és 3. L'article amb un pes 3 es pot posar a la motxilla i el benefici corresponent al el pes 4 és 2, així que afegirem 2 a M[4][3] que es mostra a continuació:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 2 | 2 | 2 | 2 | 2 | 2 |
| 2 | 0 | 0 | 0 | 2 | 3 | 3 | 3 | 5 | 5 |
| 3 | 0 | 0 | 0 | 1 | 3 | 3 | 3 | 5 | 5 |
| 4 | 0 | 0 | 0 | 2 |
Quan i = 4, W = 4
El pes corresponent al valor 4 és 6, és a dir, w4= 6. Com que tenim quatre articles al conjunt de pesos 3, 4, 5 i 6 respectivament, i el pes de la motxilla és 4. L'article amb un pes 4 es pot posar a la motxilla i el benefici corresponent al el pes 4 és 3, així que afegirem 3 a M[4][4] que es mostra a continuació:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 2 | 2 | 2 | 2 | 2 | 2 |
| 2 | 0 | 0 | 0 | 2 | 3 | 3 | 3 | 5 | 5 |
| 3 | 0 | 0 | 0 | 1 | 3 | 3 | 3 | 5 | 5 |
| 4 | 0 | 0 | 0 | 2 | 3 |
Quan i = 4, W = 5
El pes corresponent al valor 4 és 6, és a dir, w4= 6. Com que tenim quatre articles al conjunt de pesos 3, 4, 5 i 6 respectivament, i el pes de la motxilla és 5. L'article amb un pes 4 es pot posar a la motxilla i el benefici corresponent al el pes 4 és 3, així que afegirem 3 a M[4][5] que es mostra a continuació:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 2 | 2 | 2 | 2 | 2 | 2 |
| 2 | 0 | 0 | 0 | 2 | 3 | 3 | 3 | 5 | 5 |
| 3 | 0 | 0 | 0 | 1 | 3 | 3 | 3 | 5 | 5 |
| 4 | 0 | 0 | 0 | 2 | 3 | 3 |
Quan i = 4, W = 6
El pes corresponent al valor 4 és 6, és a dir, w4= 6. Com que tenim quatre articles en el conjunt de pesos 3, 4, 5 i 6 respectivament, i el pes de la motxilla és 6. En aquest cas, podem posar els articles a la motxilla qualsevol dels pes 3, 4 , 5 o 6 però el benefici, és a dir, 4 corresponent al pes 6 és el més alt entre tots els articles; per tant, afegim 4 a M[4][6] que es mostra a continuació:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 2 | 2 | 2 | 2 | 2 | 2 |
| 2 | 0 | 0 | 0 | 2 | 3 | 3 | 3 | 5 | 5 |
| 3 | 0 | 0 | 0 | 1 | 3 | 3 | 3 | 5 | 5 |
| 4 | 0 | 0 | 0 | 2 | 3 | 3 | 4 |
Quan i = 4, W = 7
El pes corresponent al valor 4 és 6, és a dir, w4= 6. Com que tenim quatre articles al conjunt de pesos 3, 4, 5 i 6 respectivament, i el pes de la motxilla és 7. Aquí, si afegim dos articles de pesos 3 i 4, es produirà el màxim. benefici, és a dir, (2 + 3) és igual a 5, de manera que sumem 5 a M[4][7] que es mostra a continuació:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 2 | 2 | 2 | 2 | 2 | 2 |
| 2 | 0 | 0 | 0 | 2 | 3 | 3 | 3 | 5 | 5 |
| 3 | 0 | 0 | 0 | 2 | 3 | 3 | 3 | 5 | 5 |
| 4 | 0 | 0 | 0 | 2 | 3 | 3 | 4 | 5 |
Quan i = 4, W = 8
El pes corresponent al valor 4 és 6, és a dir, w4= 6. Com que tenim quatre articles al conjunt de pesos 3, 4, 5 i 6 respectivament, i el pes de la motxilla és 8. Aquí, si afegim dos articles de pesos 3 i 4, es produirà el màxim. benefici, és a dir, (2 + 3) és igual a 5, de manera que sumem 5 a M[4][8] que es mostra a continuació:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 2 | 2 | 2 | 2 | 2 | 2 |
| 2 | 0 | 0 | 0 | 2 | 3 | 3 | 3 | 5 | 5 |
| 3 | 0 | 0 | 0 | 2 | 3 | 3 | 3 | 5 | 5 |
| 4 | 0 | 0 | 0 | 2 | 3 | 3 | 4 | 5 | 5 |
Com podem observar a la taula anterior que 5 és el benefici màxim entre totes les entrades. El punter apunta a l'última fila i l'última columna amb un valor de 5. Ara compararem el valor 5 amb la fila anterior; si la fila anterior, és a dir, i = 3 conté el mateix valor 5, el punter es desplaçarà cap amunt. Com que la fila anterior conté el valor 5, el punter es desplaçarà cap amunt tal com es mostra a la taula següent:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 2 | 2 | 2 | 2 | 2 | 2 |
| 2 | 0 | 0 | 0 | 2 | 3 | 3 | 3 | 5 | 5 |
| 3 | 0 | 0 | 0 | 2 | 3 | 3 | 3 | 5 | 5 |
| 4 | 0 | 0 | 0 | 2 | 3 | 3 | 4 | 5 | 5 |
De nou, compararem el valor 5 de la fila anterior, és a dir, i = 2. Com que la fila de dalt conté el valor 5, el punter es tornarà a moure cap amunt tal com es mostra a la taula següent:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 2 | 2 | 2 | 2 | 2 | 2 |
| 2 | 0 | 0 | 0 | 2 | 3 | 3 | 3 | 5 | 5 |
| 3 | 0 | 0 | 0 | 2 | 3 | 3 | 3 | 5 | 5 |
| 4 | 0 | 0 | 0 | 2 | 3 | 3 | 4 | 5 | 5 |
De nou, compararem el valor 5 de la fila anterior, és a dir, i = 1. Com que la fila anterior no conté el mateix valor, considerarem la fila i=1, i el pes corresponent a la fila és 4. Per tant , hem seleccionat el pes 4 i hem rebutjat els pesos 5 i 6 que es mostren a continuació:
x = { 1, 0, 0}
El benefici corresponent al pes és 3. Per tant, el benefici restant és (5 - 3) igual a 2. Ara compararem aquest valor 2 amb la fila i = 2. Com que la fila (i = 1) conté el valor 2 ; per tant, el punter es va desplaçar cap amunt que es mostra a continuació:
convertir cadena en enter
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 2 | 2 | 2 | 2 | 2 | 2 |
| 2 | 0 | 0 | 0 | 2 | 3 | 3 | 3 | 5 | 5 |
| 3 | 0 | 0 | 0 | 2 | 3 | 3 | 3 | 5 | 5 |
| 4 | 0 | 0 | 0 | 2 | 3 | 3 | 4 | 5 | 5 |
De nou comparem el valor 2 amb una fila superior, és a dir, i = 1. Com que la fila i = 0 no conté el valor 2, es seleccionarà la fila i = 1 i es mostrarà el pes corresponent a i = 1. baix:
X = {1, 1, 0, 0}
El benefici corresponent al pes és 2. Per tant, el benefici restant és 0. Comparem el valor 0 amb la fila anterior. Com que la fila anterior conté un valor 0, però el benefici corresponent a aquesta fila és 0. En aquest problema, es seleccionen dos pesos, és a dir, 3 i 4 per maximitzar el benefici.