Ниже мы рассмотрим программу в Excel VBA, которая решает небольшой экземпляр задачи о рюкзаке.

Определение: Данный набор элементов, каждый из которых имеет вес и значение, определяют элементы для включения в коллекции, так что общее значение как можно больше, а общий вес меньше заданного предела.

Он получил свое название от проблемы, с которыми сталкиваются, кто ограничен в связи с фиксированным размером рюкзака и должны заполнить его с наиболее полезными предметами.

Пример: 5 элементов с весами, значением и пределом, приведенные.

Knapsack Problem Image

В Excel эта проблема выглядит следующим образом:

Knapsack Problem Example

  1. Во-первых, мы объявляем пять переменных типа Double с ограничением имен, вес, стоимость, общую массу и maximumValue.

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

  1. Далее, мы объявляем пять переменных типа Integer с с именами I, J, K, L, м.

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

  1. Мы инициализируем две переменные. Мы инициализируем переменный предел со значением ячейки D6. Мы инициализируем переменную maximumValue со значением 0.

limit = Range("D6").value

maximumValue = 0

  1. Далее, мы проверяем каждое возможное решение. Мы можем либо включить пункт (1) или оставить его (0). Мы начинаем 5 For Next петель. Один для каждого пункта.

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

  1. Вычислим вес и стоимость возможного решения.

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

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

  1. Только если значение больше, чем maximumValue и вес ниже предела, мы нашли новое лучшее решение.

If value > maximumValue And weight <= limit Then

  1. Если это так, то записать новое решение строки 4, вес на общую массу и значение maximumValue.

Range("B4").value = i

Range("C4").value = j

Range("D4").value = k

Range("E4").value = l

Range("F4").value = m

totalWeight = weight

maximumValue = value

  1. Не забудьте закрыть, если заявление.

End If

  1. Не забудьте закрыть 5 For Next петель.

Next m

Next l

Next k

Next j

Next i

Excel VBA проверяет каждый из возможных решений таким образом, и в результате оптимальное решение будет отображаться в строке 4. Помните, что 1 означает, что мы включаем в себя элемент, 0 означает, что мы его опускают.

  1. И, наконец, написать общую массу и maximumValue оптимального решения, чтобы соответственно ячейку B6 и B8.

Range("B6").value = totalWeight

Range("B8").value = maximumValue

  1. Тест программы.

Результат:

Knapsack Problem Result

Вывод: это оптимальное включить последние четыре элемента с максимальным значением 15. Это решение с общей массой 2 + 1 + 1 + 4 = 8 не превышает предела 15.

Примечание: путем вес и значение переменного можно решить любую проблему рюкзака этого размера (см загружаемого файл Excel).