Задание 27
тема 4 из 9

Целевая функция и оптимальное размещение

Целевая функция — величина, которую нужно сделать наименьшей или наибольшей, записанная формулой через выбор, который мы делаем. В задачах о размещении склада она равна сумме стоимостей доставки: число грузов, умноженное на расстояние до каждого пункта. Для файла A её считают перебором всех мест, а для файла B — пересчётом при сдвиге места на соседний пункт.

Часто в задании27На карте навыков

Как составить и найти целевую функцию

Пункты стоят на дороге в точках x1,…,xNx_1, \ldots, x_N, из пункта ii везут wiw_i грузов. Склад ставят в одном из пунктов.

  • Целевая функция: C(j)=∑iwi⋅∣xi−xj∣C(j) = \sum_i w_i \cdot |x_i - x_j| — стоимость, если склад в пункте jj. Ответ — наименьшее C(j)C(j).
  • Число контейнеров вместимостью VV для tt предметов — округление вверх: ⌈t/V⌉\lceil t / V \rceil, в Python (t + V - 1) // V.
  • На кольце из NN пунктов расстояние равно min⁡(d,N−d)\min(d, N - d).
  • Перебор всех jj с суммой внутри — O(N2)O(N^2), только для файла A.
  • Сдвиг склада вправо на dd: C(j+1)=C(j)+d⋅(L−R)C(j + 1) = C(j) + d \cdot (L - R), где LL — сумма весов пунктов до jj включительно, RR — остальных.

Целевая функция и ограничения

Математическая модель практической задачи состоит из трёх частей. Переменные — то, что мы выбираем: номер пункта для склада. Ограничения — условия, которым выбор обязан удовлетворять: склад стоит в одном из пунктов, контейнер вмещает не больше VV предметов. Целевая функция — величина, которую нужно сделать наименьшей или наибольшей, записанная формулой через переменные.

Для склада на прямой дороге стоимость доставки из пункта ii — число грузов wiw_i, умноженное на расстояние ∣xi−xj∣|x_i - x_j|. Целевая функция — сумма этих стоимостей по всем пунктам: C(j)=∑iwi⋅∣xi−xj∣C(j) = \sum_i w_i \cdot |x_i - x_j|. Составьте её по условию и проверьте на примере из условия, прежде чем писать быструю программу.

Пример

Магазины стоят на дороге на 2-м, 5-м и 9-м километре, им нужно 4, 2 и 3 доставки. Склад ставят у одного из магазинов, стоимость — число доставок, умноженное на расстояние. Где поставить склад?

  1. 1.C(2)=4⋅0+2⋅3+3⋅7=27C(2) = 4 \cdot 0 + 2 \cdot 3 + 3 \cdot 7 = 27.
  2. 2.C(5)=4⋅3+2⋅0+3⋅4=24C(5) = 4 \cdot 3 + 2 \cdot 0 + 3 \cdot 4 = 24.
  3. 3.C(9)=4⋅7+2⋅4+3⋅0=36C(9) = 4 \cdot 7 + 2 \cdot 4 + 3 \cdot 0 = 36.
  4. 4.Наименьшая стоимость 24 у магазина на 5-м километре. Программа печатает три пары: место и стоимость.

Ответ: 5-й километр, стоимость 24

Число контейнеров: округление вверх

Если предметы везут в контейнерах вместимостью VV, а неполный контейнер всё равно едет целиком, число контейнеров для tt предметов — округление вверх: ⌈t/V⌉\lceil t / V \rceil. Это вес пункта в целевой функции. Деление t // V округляет вниз и теряет неполный контейнер.

В целых числах округление вверх записывают как (t + V - 1) // V. Если tt делится на VV, прибавка V−1V - 1 не даёт нового контейнера, иначе даёт ровно один.

Пример

Контейнер вмещает 36 пробирок. Сколько контейнеров нужно для 100, 72, 73 и 5 пробирок?

  1. 1.100: (100+35)//36=135//36=3(100 + 35) // 36 = 135 // 36 = 3, два полных контейнера и один на 28 пробирок.
  2. 2.72: 107//36=2107 // 36 = 2, ровно два полных.
  3. 3.73: 108//36=3108 // 36 = 3, одна пробирка требует третьего контейнера.
  4. 4.5: 40//36=140 // 36 = 1. Программа печатает те же числа.

Ответ: 3, 2, 3 и 1

Перебор всех мест

Самая простая программа перебирает все пункты jj и для каждого считает C(j)C(j) циклом по всем пунктам. Это N2N^2 шагов: для файла A из сотни строк — мгновенно, для файла B из миллионов строк — слишком долго, подробнее в теме файл A и файл B. Перебор нужен, чтобы проверить быструю программу на файле A и на примере из условия.

Пример

Пункты на 1-м, 2-м, 5-м, 7-м, 8-м и 10-м километре сдают 100, 200, 4, 3, 2 и 190 пробирок, контейнер вмещает 96 пробирок. Лабораторию ставят в одном из пунктов, стоимость — число контейнеров, умноженное на расстояние. Найдите наименьшую стоимость.

  1. 1.Числа контейнеров: 2, 3, 1, 1, 1, 2.
  2. 2.Для лаборатории на 2-м километре: 2⋅1+3⋅0+1⋅3+1⋅5+1⋅6+2⋅8=322 \cdot 1 + 3 \cdot 0 + 1 \cdot 3 + 1 \cdot 5 + 1 \cdot 6 + 2 \cdot 8 = 32.
  3. 3.Для лаборатории на 5-м километре стоимость тоже 32, для остальных пунктов она больше. Программа читает данные из файла и печатает 32.
f = open('27_A.txt')cap = 96n = int(f.readline())x = []w = []for i in range(n):    p, t = map(int, f.readline().split())    x.append(p)    w.append((t + cap - 1) // cap)best = Nonefor j in range(n):    cost = sum(w[i] * abs(x[i] - x[j]) for i in range(n))    if best is None or cost < best:        best = costprint(best)

Ответ: 3232

Расстояние на кольцевой дороге

На кольцевой трассе длиной NN с пунктами через 1 км можно ехать в обе стороны. Между пунктами cc и pp по одной стороне d=∣p−c∣d = |p - c| км, по другой N−dN - d км, и машина едет по короткой: расстояние равно min⁡(d,N−d)\min(d, N - d). Целевая функция та же сумма, только с этим расстоянием. Быстрый расчёт для кольца разобран в теме кольцо: утроенный список.

Пример

На кольце длиной 6 км пункты стоят на каждом километре, им нужно 8, 20, 5, 13, 7 и 19 комплектов. Стоимость — число комплектов, умноженное на расстояние. В каком пункте поставить цех?

  1. 1.Для цеха в пункте 6 расстояния до пунктов 1–5 равны 1, 2, 3, 2, 1: до пунктов 1 и 2 короче ехать вперёд через нулевой километр.
  2. 2.C(6)=8⋅1+20⋅2+5⋅3+13⋅2+7⋅1+19⋅0=96C(6) = 8 \cdot 1 + 20 \cdot 2 + 5 \cdot 3 + 13 \cdot 2 + 7 \cdot 1 + 19 \cdot 0 = 96.
  3. 3.Программа перебирает все шесть пунктов и печатает 6 96: меньше 96 нет.

Ответ: пункт 6, стоимость 96

Пересчёт стоимости при сдвиге склада

Пусть пункты упорядочены по возрастанию xx. Сдвинем склад из пункта jj в соседний пункт j+1j + 1, на d=xj+1−xjd = x_{j+1} - x_j км. Все пункты до jj включительно стали дальше на dd, а пункты от j+1j + 1 — ближе на dd. Поэтому C(j+1)=C(j)+d⋅(L−R)C(j + 1) = C(j) + d \cdot (L - R), где LL — сумма весов пунктов до jj включительно, RR — сумма весов остальных.

Посчитайте CC для первого пункта одним циклом, затем идите вправо и пересчитывайте CC, LL и RR за несколько действий. Вся программа — O(N)O(N). Стоимость убывает, пока LL меньше RR, поэтому лучшее место — первый пункт, на котором сумма весов от начала до него включительно доходит до половины общей суммы.

f = open('27_A.txt')cap = 36n = int(f.readline())x = []w = []for i in range(n):    p, t = map(int, f.readline().split())    x.append(p)    w.append((t + cap - 1) // cap)cost = 0for i in range(n):    cost += w[i] * (x[i] - x[0])best = costleft = 0right = sum(w)for i in range(n - 1):    left += w[i]    right -= w[i]    cost += (x[i + 1] - x[i]) * (left - right)    best = min(best, cost)print(best)

Пример задания

Открытый банк ФИПИ

У медицинской компании есть N пунктов приёма биоматериалов на анализ. Все пункты расположены вдоль автомагистрали и имеют номера, соответствующие расстоянию от нулевой отметки до конкретного пункта. Известно количество пробирок, которое ежедневно принимают в каждом из пунктов. Пробирки перевозят в специальных транспортировочных контейнерах вместимостью не более 36 штук. Каждый транспортировочный контейнер упаковывается в пункте приёма и вскрывается только в лаборатории. Стоимость перевозки биоматериалов равна произведению расстояния от пункта до лаборатории на количество контейнеров с пробирками. Общая стоимость перевозки за день равна сумме стоимостей перевозок из каждого пункта в лабораторию. Лабораторию расположили в одном из пунктов приёма биоматериалов таким образом, что общая стоимость доставки биоматериалов из всех пунктов минимальна. Определите минимальную общую стоимость доставки биоматериалов из всех пунктов приёма в лабораторию.

Входные данные
Дано два входных файла (файл A и файл B), каждый из которых в первой строке содержит число N (1 ≤ N ≤ 10 000 000) – количество пунктов приёма биоматериалов. В каждой из следующих N строк находится два числа: номер пункта и количество пробирок в этом пункте (все числа натуральные, количество пробирок в каждом пункте не превышает 1000). Пункты перечислены в порядке их расположения вдоль дороги, начиная от нулевой отметки.
В ответе укажите два числа: сначала значение искомой величины для файла А, затем – для файла B.

Типовой пример организации данных во входном файле
6
1 100
2 200
5 4
7 3
8 2
10 190
При таких исходных данных и вместимости транспортировочного контейнера, составляющей 96 пробирок, компании выгодно открыть лабораторию в пункте 2. В этом случае сумма транспортных затрат составит: 1 ꞏ 2 + 3 ꞏ 1 + 5 ꞏ 1 + 6 ꞏ 1 + 8 ꞏ 2.

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

59136_27_A.txt

59136_27_B.txt

Потренируйте навык

Все задания на этот навык

Решать