Комбинаторная оптимизация

Точный рюкзак с ограниченной ёмкостью и TSP полным перебором до девяти точек.

Решите небольшой рюкзак динамическим программированием или точный TSP полным перебором.

Пример расчёта — замените данные своими

Максимальная ценность

Подробности — в методике ниже

Расчёт по шагам

Динамическое программирование обходит вместимости в обратном порядке, поэтому каждый предмет используется не более одного раза.
Сложность O(n×capacity), предел вместимости 10.

Подробная таблица (2 строк)

Подробный результат расчёта
Предмет	Вес	Ценность
A	6	30
C	4	16

Загружаем калькулятор…

Рюкзак 0/1 решается точным динамическим программированием по целой вместимости. TSP фиксирует старт и перебирает все перестановки остальных точек.

Рюкзак: до 20 предметов и вместимость до 10 000. TSP: 3–9 точек; при девяти проверяется 8!=40320 маршрутов. Не поддерживаются дробные веса, временные окна и неевклидовы расстояния.

Для прямоугольника (0,0),(3,0),(3,4),(0,4) кратчайший замкнутый маршрут имеет длину 14.

Версия методики: 1.0.0