Цепочки коробок и пары

Коробки со сторонами 12, 18, 21, 27, 34, 40 и 45; одну можно вложить в другую, если её сторона меньше хотя бы на 6. Как вложить друг в друга как можно больше коробок?

Строить цепочку снаружи: в каждую коробку класть самую большую из тех, что в неё помещаются. Большая коробка внутри оставляет больше места для следующих.

Начнём снаружи. Самая большая коробка — 45. В неё можно поместить коробку размером не больше 45 − 6 = 39. Из подходящих выбираем самую большую — 34. Почему не 12? Потому что после выбора 12 внутри почти не останется возможностей; коробка 34 оставляет больше места для последующих вложений.

Получилась цепочка 45 → 34 → 27 → 21 → 12 — пять коробок. Код: размеры по убыванию, коробка берётся, если она меньше последней выбранной хотя бы на зазор. Самая маленькая коробка — 12: это ответ на частый второй вопрос «наибольший размер самой маленькой коробки».

sizes = [12, 18, 21, 27, 34, 40, 45]gap = 6sizes.sort(reverse=True)selected = []for size in sizes:    if not selected or selected[-1] - size >= gap:        selected.append(size)print(len(selected), selected[-1])

Здесь предполагается, что исходный список непустой и gap > 0. Условие not selected истинно, пока цепочка пуста: первая, самая большая коробка берётся без проверки. Благодаря короткому вычислению or к selected[-1] пустого списка программа не обращается.

А если второй вопрос — «наименьший размер внешней коробки»?

Строить цепочку изнутри наружу: начать с самой маленькой и каждый раз брать самую маленькую коробку, в которую влезает предыдущая. Строй с той стороны, которую оптимизирует второй критерий.

Рассуждение то же, только зеркальное: маленькая внешняя коробка на каждом шаге оставляет больше выбора для следующей.

sizes = [12, 18, 21, 27, 34, 40, 45]gap = 6chain = []for size in sorted(sizes):    if not chain or size - chain[-1] >= gap:        chain.append(size)print(*chain)

Пять коробок, внешняя имеет размер 40, а снаружи внутрь внешней была 45. Количество одинаковое, а второе число зависит от направления: строй от той стороны, которую оптимизирует второй критерий.

Этот разбор предполагает одинаковый минимальный зазор между соседними коробками и отсутствие других ограничений. Материалы и цвета, которые должны чередоваться, или зазор, растущий с номером коробки, — это усложнения из дополнительного урока: для них нужно новое обоснование.

В лодку садятся не больше двух человек, суммарная масса не больше вместимости. Как перевезти всех за наименьшее число рейсов?

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

Указатель здесь — обычная переменная, хранящая индекс текущего элемента: left = 0 стоит в начале списка, right = len(a) - 1 — в конце.

Предполагается, что любой человек может ехать один. Если самый тяжёлый не помещается даже с самым лёгким, ни с кем другим он тоже не поместится — значит, едет один.

w = [80, 130, 50, 100, 70, 60]capacity = 150w.sort()left = 0right = len(w) - 1trips = 0while left <= right:    if left < right and w[left] + w[right] <= capacity:        left += 1    right -= 1    trips += 1print(trips)

При совместной поездке двигаются оба индекса: использованы два человека. Если вместе не помещаются, используется только тяжёлый — двигается правый индекс. При left == right остался один человек, и условие left < right не позволяет использовать его дважды. Каждый указатель проходит список один раз, поэтому после сортировки работа — O(N).

Ограничение «не более двух» существенно. Для произвольного числа объектов в рейсе этот алгоритм уже не является решением общей задачи упаковки.

Грузы и контейнеры даны двумя списками, в контейнер помещается один груз. Как отправить как можно больше грузов?

Идти по грузам от лёгких и каждому отдавать самый маленький из подходящих контейнеров. Большие контейнеры остаются тяжёлым грузам.

Иногда в строке файла два числа, которые не связаны между собой: масса груза и вместимость контейнера, причём каждый контейнер берёт один груз любой массы, не большей его вместимости. Это то самое исключение из правила «сортировать записи целиком»: грузы и контейнеры — два отдельных списка, и сортируют их по отдельности.

Пусть массы грузов 15, 40, 25, 48, 30, а вместимости контейнеров 20, 10, 50, 35, 45. Лёгкие грузы получают самые маленькие подходящие контейнеры: 15 → 20, 25 → 35, 30 → 45, 40 → 50, а для 48 контейнера уже нет. Отправлено 4 груза.

Почему так правильно? Самому лёгкому грузу подходит любой контейнер, подходящий другим; отдавая ему самый маленький, мы сохраняем большие контейнеры для тяжёлых грузов — снова «оставить больше возможностей».

Второй вопрос — наибольшая масса отправленного груза при максимальном количестве — решается приёмом из подтемы 2: закрепляем k − 1 = 3 самых лёгких груза в их самых маленьких контейнерах (20, 35, 45), а последний груз берём наибольший из тех, что помещаются в самый большой из оставшихся контейнеров — 50. Это 48, а не 40.

goods = sorted([15, 40, 25, 48, 30])boxes = sorted([20, 10, 50, 35, 45])count = j = 0for g in goods:    while j < len(boxes) and boxes[j] < g:        j += 1    if j == len(boxes):        break    count += 1    j += 1 used = [False] * len(boxes)j = 0for g in goods[:count - 1]:    while boxes[j] < g:        j += 1    used[j] = True    j += 1room = max(b for b, u in zip(boxes, used) if not u)print(count, max(g for g in goods[count - 1:] if g <= room))

Первый цикл считает количество, второй закрепляет k − 1 самых лёгких грузов: [False] * len(boxes) отмечает, какие контейнеры они заняли. Указатель j по контейнерам только растёт: контейнер, который мал для лёгкого груза, тем более мал для следующих, более тяжёлых.

Изделие собирают из детали A и детали B, размеры которых отличаются не больше чем на D. Как собрать больше изделий с наибольшей прибылью?

Отсортировать оба списка по убыванию и соединять крупнейшие совместимые детали; деталь, которой нет пары, пропускать.

Прибыль — сумма размеров, все размеры положительные. Сортируем оба списка по убыванию. Если самая большая A больше самой большой B более чем на D, эта A не подойдёт ни к одной оставшейся B — её можно пропустить. Аналогично для слишком большой B. Если крупнейшие совместимы — объединяем их.

Пусть A = 50, 42, 30, 12, B = 47, 33, 20, 18, D = 5. Пара 50 и 47 подходит; 42 больше 33 + 5 — деталь 42 пропускаем; 30 и 33 подходят; 20 больше 12 + 5 — пропускаем 20, затем и 18. Получаем 2 изделия с прибылью 97 + 63 = 160.

a = sorted([50, 42, 30, 12], reverse=True)b = sorted([47, 33, 20, 18], reverse=True)distance = 5i = j = 0count = profit = 0while i < len(a) and j < len(b):    if a[i] > b[j] + distance:        i += 1    elif b[j] > a[i] + distance:        j += 1    else:        count += 1        profit += a[i] + b[j]        i += 1        j += 1print(count, profit)

• Снаружи внутрьв каждую — самую большую подходящую
• Изнутри наружуесли второй критерий — внешняя коробка
• Рейсы по двоетяжёлый с лёгким, два указателя
• Грузы и контейнерылёгкий груз — в самый маленький подходящий
• Детали A и Bкрупнейшие совместимые, лишнюю пропустить
• Обоснованиевыбор оставляет больше возможностей