🎒 Задача о рюкзаке

Это — мой проект по Прикладной математике за 2 курс.

Что за рюкзак?

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

Проект представляет из себя страницу с интерфейсом для ввода произвольных параметров задачи мультипликативного N-мерного рюкзака. Также можно включить ограниченность предметов.

Технические детали

Основная структура данных:

// Свойства:
properties: [{
  name: String, 
  maximize: Boolean
}],
// Предметы:
items: [{
  name: String,
  properties: [{
    name: String // — привязано к name в properties
    value: Number
  }],
  stock: Number (if config.stock is true)
}],
// Рюкзаки:
backpacks: [{
  // Ограничения по свойствам в сумме:
  restrictions: [{
    property: String, // — привязано к name в properties
    value: Number,
    enabled: Boolean
  }],
  // Предметы в рюкзаке (заполняется программно):
  items: [{
    ...item,
    quantity: Number
  }]
}],
config: {
  stock: Boolean // — ограничивать ли количество предметов
  // ...
}

Расчёт выполняется в фоне с помощью веб-воркера (/public/js/worker.js). В основе его функции solve лежит рекурсивный жадный алгоритм, который первым делом сортирует предметы по их эффективности.

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

Далее при добавлении предметов в комбинацию есть смысл попытаться добавить сразу несколько одинаковых предметов. Для этого используется бинарный поиск. Особенно большой прирост производительности он даёт в случаях когда в рюкзак влезает очень много предметов, потому что его сложность — O(log(n)).

В общем, алгоритм выглядит так:

# Инициализация;
  
# Обработка рюкзаков:
  Для каждого рюкзака:
    - Инициализация переменных рюкзака;
    - Фильтрация активных ограничений;
    
    # Расчёт эффективности предметов (жадный алгоритм — тут)
      Для каждого доступного предмета:
        - Вычисление приоритетного значения;
        - Расчёт отношения к ограничениям;
        - Определение максимального количества;
      - Сортировка по эффективности
    
    # Рекурсивный поиск лучшей комбинации (метод ветвей и границ — тут)
      - Проверка потенциала ветки;
        - Расчёт максимально возможного значения;
        - Сравнение с текущим лучшим;
      	- Обновление лучшего результата
      
      # Добавление предметов в комбинацию
        Для каждого предмета начиная с текущей глубины:
          - Расчёт максимально возможного количества при ограничениях
          
          # Вычисление количества предмета (бинарный поиск — тут)
            - Проверка возможности добавления
            - Обновление сумм свойств
            - Углубление в рекурсию
    
    # Сохранение результатов
    
   	# Обновление остатков

# Возврат результата

Вот так и живём.

Как хостить

1. git clone https://github.com/intredford/knapsack-problem

2. Раздайте получившуюся папку статическим сервером.