Контейнеры двух масс

Последовательность применённых правил и переходов в пунктах задачи.

Учебный авторский материал. Порядок изучения не означает новую экспертную проверку решения или проверку источников.

Что разобрать сначала

Переходите по порядку или откройте то правило, которое вызвало затруднение. В конкретном решении используются только нужные для его условия ветви.

  1. Места для тяжёлых и лёгких контейнеров
  2. Достижение минимального числа кораблей

    Сначала: Места для тяжёлых и лёгких контейнеров

  3. Ответ: да

    Сначала: Достижение минимального числа кораблей

  4. Места для тяжёлых и лёгких контейнеров

    Сначала: Ответ: да

  5. Достижение минимального числа кораблей

    Сначала: Места для тяжёлых и лёгких контейнеров

  6. Ответ: нет

    Сначала: Достижение минимального числа кораблей

  7. Места для тяжёлых и лёгких контейнеров

    Сначала: Ответ: нет

  8. Достижение минимального числа кораблей

    Сначала: Места для тяжёлых и лёгких контейнеров

  9. Ответ

    Сначала: Достижение минимального числа кораблей

Разобранный пример

Имеются контейнеры массой в 2 тонны и 7 тонн и корабли грузоподъемностью в 10 тонн.

а) Можно ли 11 контейнеров массой 7 тонн и 22 контейнера массой 2 тонны погрузить на 14 кораблей?

б) Можно ли 11 контейнеров массой 7 тонн и 17 контейнеров массой 2 тонны погрузить на 12 кораблей?

в) Какое наименьшее количество кораблей требуется для погрузки 11 контейнеров массой 7 тонн и 77 контейнеров массой 2 тонны?

Посмотреть решение

Предварительное решение, не проверено экспертом.

Ранее доступное решение переведено в общий параметрический рецепт; новая независимая проверка не проводилась.

Шаг 1. Два тяжёлых контейнера не помещаются на один корабль, поэтому для hh тяжёлых контейнеров нужно не меньше hh кораблей. Рядом с одним тяжёлым помещается не больше u=⌊C−HL⌋u=\left\lfloor \frac{C-H}{L}\right\rfloor лёгких, а на корабле без тяжёлых - не больше v=⌊CL⌋v=\left\lfloor \frac{C}{L}\right\rfloor лёгких. Значит, при mm кораблях лёгких не больше uh+v(m−h)uh+v(m-h).
H=7H=7
L=2L=2
C=10C=10
x=11x=11
y=22y=22
Шаг 2. На каждый из hh кораблей кладём один тяжёлый и, пока они есть, до uu лёгких контейнеров. Оставшиеся лёгкие распределяем по vv штук на дополнительных кораблях. Это достигает нижней границы h+⌈max⁡(0, l−uh)v⌉h+\left\lceil \frac{\max(0,\,l-uh)}{v}\right\rceil. В таблице сгруппированы одинаковые загрузки и указано количество кораблей каждого вида.
T=((0;1;1);(0;5;2);(1;1;11))\mathcal T=\left(\left(0;1;1\right);\left(0;5;2\right);\left(1;1;11\right)\right)
Шаг 3. Да. Приведённая конструкция удовлетворяет условию.
Шаг 1. Два тяжёлых контейнера не помещаются на один корабль, поэтому для hh тяжёлых контейнеров нужно не меньше hh кораблей. Рядом с одним тяжёлым помещается не больше u=⌊C−HL⌋u=\left\lfloor \frac{C-H}{L}\right\rfloor лёгких, а на корабле без тяжёлых - не больше v=⌊CL⌋v=\left\lfloor \frac{C}{L}\right\rfloor лёгких. Значит, при mm кораблях лёгких не больше uh+v(m−h)uh+v(m-h).
H=7H=7
L=2L=2
C=10C=10
x=11x=11
y=17y=17
Шаг 2. На каждый из hh кораблей кладём один тяжёлый и, пока они есть, до uu лёгких контейнеров. Оставшиеся лёгкие распределяем по vv штук на дополнительных кораблях. Это достигает нижней границы h+⌈max⁡(0, l−uh)v⌉h+\left\lceil \frac{\max(0,\,l-uh)}{v}\right\rceil. В таблице сгруппированы одинаковые загрузки и указано количество кораблей каждого вида.
T=((0;1;1);(0;5;1);(1;1;11))\mathcal T=\left(\left(0;1;1\right);\left(0;5;1\right);\left(1;1;11\right)\right)
Шаг 3. Нет. Необходимая граница или полная конечная область исключает этот случай.
Шаг 1. Два тяжёлых контейнера не помещаются на один корабль, поэтому для hh тяжёлых контейнеров нужно не меньше hh кораблей. Рядом с одним тяжёлым помещается не больше u=⌊C−HL⌋u=\left\lfloor \frac{C-H}{L}\right\rfloor лёгких, а на корабле без тяжёлых - не больше v=⌊CL⌋v=\left\lfloor \frac{C}{L}\right\rfloor лёгких. Значит, при mm кораблях лёгких не больше uh+v(m−h)uh+v(m-h).
H=7H=7
L=2L=2
C=10C=10
x=11x=11
y=77y=77
Шаг 2. На каждый из hh кораблей кладём один тяжёлый и, пока они есть, до uu лёгких контейнеров. Оставшиеся лёгкие распределяем по vv штук на дополнительных кораблях. Это достигает нижней границы h+⌈max⁡(0, l−uh)v⌉h+\left\lceil \frac{\max(0,\,l-uh)}{v}\right\rceil. В таблице сгруппированы одинаковые загрузки и указано количество кораблей каждого вида.
T=((0;1;1);(0;5;13);(1;1;11))\mathcal T=\left(\left(0;1;1\right);\left(0;5;13\right);\left(1;1;11\right)\right)
Шаг 3. Записываем найденное значение.
2525

Открыть задачу целиком

Попробовать самостоятельно