Книга Теоретический минимум по Computer Science. Все что нужно программисту и разработчику, страница 21 – Владстон Феррейра Фило

День с самой низкой ценой перед днем 3, но не в день 3 — это B(2). Потому для B(3):

• P(3) < цена в день B(2) —> B(3) = 3.

• P(3) ≥ цена в день B(2) —> B(3) = B(2).

Обратите внимание, что день с самой низкой ценой перед днем 4 будет B(3). Фактически для каждого n день с самой низкой ценой перед днем n — B(n — 1). Мы можем это использовать, чтобы выразить B(n) через B(n — 1):

Когда у нас есть все пары [n, B(n)] для для каждого дня n, решением является пара, которая дает самую высокую прибыль. Следующий алгоритм решает задачу, вычисляя все значения B снизу вверх:

function trade_dp(P)

····B[1] ← 1

····sell_day ← 1

····best_profit ← 0

····for each n from 2 to P.length

········if P[n] < P[B[n-1]]

············B[n] ← n

········else

············B[n] ← B[n-1]

········profit ← P[n] — P[B[n]]

········if profit > best_profit

············sell_day ← n

············best_profit ← profit

····return (sell_day, B[sell_day])

Алгоритм выполняет фиксированное число простых операций для каждого элемента входного списка, следовательно, он имеет сложность O(n). Это огромный рывок в производительности по сравнению со сложностью предыдущего алгоритма O(n log n) — и совершенно несравнимо со сложностью O(n²) метода полного перебора. Этот алгоритм также имеет пространственную сложность O(n), поскольку вспомогательный вектор B содержит столько же элементов, что и входные данные. Из приложения IV вы узнаете, как сэкономить память за счет создания алгоритма с пространственной сложностью O(1).

Многие задачи связаны с минимизацией или максимизацией целевого значения: найти кратчайший путь, получить наибольшую прибыль и т. д. Такие задачи называются задачами оптимизации. Когда решением является последовательность вариантов, мы часто используем стратегию ветвей и границ. Ее цель состоит в том, чтобы выиграть время за счет быстрого обнаружения и отбрасывания плохих вариантов. Чтобы понять, каким образом они ищутся, мы сначала должны разобраться в понятиях «верхняя граница» и «нижняя граница».

Границы обозначают диапазон значения. Верхняя граница устанавливает предел того, каким высоким оно может быть. Нижняя граница — это наименьшее значение, на которое стоит надеяться; она гарантирует, что любое значение либо равно ей, либо ее превышает.

Мы порой легко находим решения, близкие к оптимальным: короткий путь — но, возможно, не самый короткий; большая прибыль — но, возможно, не максимальная. Они дают границы оптимального решения. К примеру, любой короткий маршрут из одной точки в другую никогда не будет короче расстояния между ними по прямой. Следовательно, расстояние по прямой является нижней границей самого короткого пути.

В задаче о жадном грабителе и рюкзаке (см. раздел «Эвристические алгоритмы»

function powdered_knapsack(items, max_weight)

····bag_weight ← 0

····bag_items ← List.new

····items ← sort_by_value_weight_ratio(items)

····for each i in items

········weight ← min(max_weight — bag_weight,

·····················i.weight)

········bag_weight ← bag_weight + weight

········value ← weight * i.value_weight_ratio

········bagged_value ← bagged_value + value

········bag_items.append(item, weight)

····return bag_items, bag_value

Добавление ограничения неделимости предметов только уменьшит максимально возможную прибыль, потому что нам придется менять последнюю уложенную в рюкзак вещь на что-то подешевле. Это означает, что powdered_knapsack дает верхнюю границу оптимальной прибыли с неделимыми предметами ^[43].

Мы уже убедились, что поиск оптимальной прибыли в задаче о рюкзаке требует дорогих вычислений O(n²). Однако мы можем быстро получить верхние и нижние границы оптимальной прибыли при помощи функций powdered_knapsack и greedy_knapsack. Давайте попробуем это сделать на примере задачи о рюкзаке (табл. 3.3).

Таблица 3.3. Верхняя и нижняя границы в задаче о рюкзаке