Полиномиальный в среднем алгоритм для задачи упаковки/Задачи/ex-packing-average-bad-and-good-data

Цыганова Светлана, 974 гр.

Какие входные данные для алгоритма динамического программирования для упаковки

заставят его работать экспоненциально долго?

А какие — за ?

Решение

1) Экспоненциально долго алгоритм будет работать на частный случае подмножеств: каждое подмножество будет отвечать некоторому элементу, таким образом число подмножеств равно числу элементов, все подмножества попарно не пересекаются (диагональная матрица инцидентности). Тогда столбцов будет n. Для каждого столбца число объектов(совокупность решения, покрытия, размера покрытия) в листе X увеличивается в 2 раза (для каждого объекта на предыдущем шаге приписываем в лист ещё один объект). Таким образом для i-го столбца будет совершено прохода по внутреннему циклу, и для последнего столбца - . Таким образом после работы в X будет объектов. Чтобы их записать в X, очевидно, надо было потратить экспоненциальное время. Таким образом на данном входе алгоритм работает экспоненциальное время.