Решение задачи о ранце 0/1 с помощью алогритма имитации отжига.
Алгоритм следующий:
- Создать начальное решение;
- Оценить решение;
- Изменить решение случайным образом;
- Оценить новое решение;
- Критерий допуска;
- Уменьшение температуры.
Программа практически полностью повторяет данный алгоритм.
INPUT:
- количество индексов для ответа;
- размерность рюкзака;
- пары вес-стоимость.
OUTPUT:
- список, содержащий лучшую стоимость и комбинацию 0/1.
Начальная температура изначально выбрана равной 100.0 и определена как константа. Для большего количества итераций (100) необходимо эксперементировать со значением температуры.
Конечная темература была приравнена к 0.5 для того, чтобы алгоритм не выполнялся дольше, чем это необходимо.