300 Примера

Проблем са ранцем

Knapsack Problem

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





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

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





Слика проблема ранца

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



Пример проблема ранца

шта ф2 ради у екцелу

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

НиједанлимитКао Доубле, тежинаКао Доубле, вредностКао Доубле, Укупна масаКао Доубле, макимумВалуеКао Доубле

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

екцел користи вредност ћелије у формули
Ниједани, ј, к, л, мКао Интегер

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

лимит = Опсег ('Д6'). вредност
макимумВалуе = 0

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

Заи = 0До1
Зај = 0До1
Зак = 0До1
Зал = 0До1
Зам = 0До1

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

тежина = 12 * и + 2 * ј + 1 * к + 1 * л + 4 * м
вредност = 4 * и + 2 * ј + 2 * к + 1 * л + 10 * м

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

Аковредност> максимална вредностИтежина<= limit Онда

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

Опсег ('Б4'). Вредност = и
Опсег ('Ц4'). Вредност = ј
Опсег ('Д4'). Вредност = к
Опсег ('Е4'). Вредност = л
Опсег ('Ф4'). Вредност = м
укупна тежина = тежина
макимумВалуе = вредност

8. Не заборавите да затворите наредбу Иф.

Крај Ако

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

која је просечна формула у екцелу
Следећим
Следећитхе
Следећидо
Следећиј
Следећии

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

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

Опсег ('Б6'). Вредност = укупна тежина
Опсег ('Б8'). Вредност = максимална вредност

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

Резултат:

Резултат проблема са ранцем

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

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

11/11 Завршено! Сазнајте много више о петљама>
Идите на следеће поглавље: Макро грешке



^