Zemāk mēs apskatīsim programmu Excel VBA ka atrisina neliels piemērs a mugursomas problēma.
Definīcija. Ņemot vērā priekšmetu kopu, katrs ar svaru un vērtību, nosakiet kolekcijā iekļaujamos priekšmetus, lai kopējā vērtība būtu pēc iespējas lielāka un kopējais svars būtu mazāks par noteikto robežu. Tā nosaukums cēlies no problēmas, ar kuru saskaras kāds, kuru ierobežo fiksēta izmēra mugursoma, un tas jāaizpilda ar visnoderīgākajiem priekšmetiem.
Piemērs: 5 preces ar svariem, vērtībām un ierobežojumiem, kā norādīts.
Programmā Excel šī problēma izskatās šādi:
1. Pirmkārt, mēs deklarējam piecus Double tipa mainīgos ar nosaukumu limit, weight, value, totalWeight un maximumValue.
Dim ierobežojums As Double, svars As Double, vērtība As Double, totalWeight As Double, maximumValue Kā Double
2. Tālāk mēs deklarējam piecus Integer tipa mainīgos ar nosaukumiem i, j, k, l, m.
Dim i, j, k, l, m As Integer
3. Mēs inicializējam divus mainīgos. Mēs inicializējam mainīgo robežu ar šūnas D6 vērtību. Mēs inicializējam mainīgo maximumValue ar vērtību 0.
limits = Diapazons ("D6"). vērtība
maksimālā vērtība = 0
4. Tālāk mēs pārbaudām katru iespējamo risinājumu. Mēs varam vai nu iekļaut vienumu (1), vai arī izlaist (0). Mēs sākam 5 For Next cilpas. Viens katram priekšmetam.
Ja i = 0 līdz 1
Ja j = 0 līdz 1
Ja k = 0 līdz 1
Ja l = 0 līdz 1
Ja m = 0 līdz 1
5. Mēs aprēķinām iespējamā risinājuma svaru un vērtību.
svars = 12 * i + 2 * j + 1 * k + 1 * l + 4 * m
vērtība = 4 * i + 2 * j + 2 * k + 1 * l + 10 * m
6. Mēs esam atraduši jaunu labāku risinājumu tikai tad, ja vērtība ir lielāka par maksimālo vērtību un svars ir zemāks par ierobežojumu.
Ja vērtība> maximumValue Un svars <= limits Tad
7. Ja tā ir taisnība, mēs jauno risinājumu ierakstām 4. rindā, svars - totalWeight un vērtība - maximumValue.
Diapazons ("B4"). Vērtība = i
Diapazons ("C4"). Vērtība = j
Diapazons ("D4"). Vērtība = k
Diapazons ("E4"). Vērtība = l
Diapazons ("F4"). Vērtība = m
totalWeight = svars
maximumValue = vērtība
8. Neaizmirstiet aizvērt paziņojumu Ja.
Beigas Ja
9. Neaizmirstiet aizvērt 5 For Next cilpas.
Nākamais m
Nākamais l
Nākamais k
Nākamais j
Tālāk i
Excel VBA šādā veidā pārbauda katru iespējamo risinājumu, un rezultātā 4. rindā parādīsies optimālais risinājums. Atcerieties, ka 1 nozīmē, ka mēs iekļaujam vienumu, 0 nozīmē, ka mēs to atstājam.
10. Visbeidzot ierakstiet optimālā risinājuma totalWeight un maximumValue attiecīgi šūnās B6 un B8.
Diapazons ("B6"). Vērtība = totalWeight
Diapazons ("B8"). Vērtība = maximumValue
11. Pārbaudiet programmu.
Rezultāts:
Secinājums: optimāli ir iekļaut pēdējos četrus vienumus ar maksimālo vērtību 15. Šis risinājums ar kopējo svaru 2 + 1 + 1 + 4 = 8 nepārsniedz 15 robežu.
Piezīme: padarot svarus un vērtības mainīgus, jūs varat atrisināt jebkuru šāda izmēra mugursomas problēmu (skatiet lejupielādējamo Excel failu).
