Проблем са кнапсацком у Екцелу ВБА

У наставку ћемо погледати програм Екцел ВБА то решава мала инстанца а проблем са кнапсацком.

Дефиниција: С обзиром на скуп ставки, свака са тежином и вриједношћу, одређују ставке које треба укључити у колекцију тако да је укупна вриједност што је могуће већа и укупна тежина је мања од одређеног ограничења. Његово име произилази из проблема са којим се суочава неко ко је ограничен фиксном величином и мора га попунити са најкориснијим ставкама.

Пример: 5 ставки са теговима, вриједностима и ограничењем.

У програму Екцел овај проблем изгледа овако:

1. Прво, објављујемо пет варијабли типа Доубле са ограничењем имена, тежином, вриједношћу, ТоталВеигхт и макимумВалуе.

Dim limit As Double, weight As Double, value As Double, totalWeight As Double, maximumValue As Double

2. Затим декларишемо пет варијабли типа Интегер са именима и, ј, к, л, м.

Dim i, j, k, l, m As Integer

3. Иницијализирамо две варијабле. Иницијализирамо варијабилни лимит са вриједношћу ћелије Д6. Иницијализирамо променљиву максималну вредност са вредностом 0.

limit = Range("D6").value
maximumValue = 0

4. Затим проверавамо сва могућа решења. Можемо укључити ставку (1) или га оставити (0). Започињемо 5 за наредне петље. Један за сваку ставку.

For i = 0 To 1
    For j = 0 To 1
        For k = 0 To 1
            For l = 0 To 1
                For m = 0 To 1

5. Израчунамо тежину и вредност могућег решења.

weight = 12 * i + 2 * j + 1 * k + 1 * l + 4 * m
value = 4 * i + 2 * j + 2 * k + 1 * l + 10 * m

6. Само ако је вредност већа од максималне вредности и тежина је нижа од границе, пронашли смо ново боље рјешење.

If value > maximumValue And weight <= limit Then

7. Ако је истина, упижемо ново рјешење у ред 4, тежину до ТоталВеигхт и вриједност до макимумВалуе.

Range("B4").value = i
Range("C4").value = j
Range("D4").value = k
Range("E4").value = l
Range("F4").value = m
totalWeight = weight
maximumValue = value

8. Немојте заборавити затворити изјаву Ако.

End If

9. Немојте заборавити да затворите 5 Фор Нект петље.

                Next m
            Next l
        Next k
    Next j
Next i

Екцел ВБА провјерава свако могуће рјешење на тај начин и као резултат ће се оптимално рјешење појавити у реду 4. Запамтите, 1 значи да укључимо ставку, 0 значи да га оставимо изван.

10. Напокон, напишите ТоталВеигхт и макимумВалуе оптималног решења за ћелије Б6 и Б8.

Range("B6").value = totalWeight
Range("B8").value = maximumValue

11. Тестирајте програм.

Резултат:

Закључак: оптимално је укључити задње четири ставке са максималном вриједношћу од 15. Ово рјешење укупне тежине 2 + 1 + 1 + 4 = 8 не прелази границу од 15.

Напомена: креирањем варијабле тегова и вриједности можете ријешити било који проблем с кнапсацком ове величине (погледајте Екцел датотеку која се може преузети).