Имеются контейнеры массой в 2 тонны и 7 тонн и корабли грузоподъемностью в 10 тонн.
а) Можно ли 11 контейнеров массой 7 тонн и 22 контейнера массой 2 тонны погрузить на 14 кораблей?
б) Можно ли 11 контейнеров массой 7 тонн и 17 контейнеров массой 2 тонны погрузить на 12 кораблей?
в) Какое наименьшее количество кораблей требуется для погрузки 11 контейнеров массой 7 тонн и 77 контейнеров массой 2 тонны?
Посмотреть решение
Предварительное решение, не проверено экспертом.
Ранее доступное решение переведено в общий параметрический рецепт; новая независимая проверка не проводилась.
Шаг 1. Два тяжёлых контейнера не помещаются на один корабль, поэтому для h тяжёлых контейнеров нужно не меньше h кораблей. Рядом с одним тяжёлым помещается не больше u=⌊LC−H⌋ лёгких, а на корабле без тяжёлых - не больше v=⌊LC⌋ лёгких. Значит, при m кораблях лёгких не больше uh+v(m−h).
H=7
L=2
C=10
x=11
y=22
Шаг 2. На каждый из h кораблей кладём один тяжёлый и, пока они есть, до u лёгких контейнеров. Оставшиеся лёгкие распределяем по v штук на дополнительных кораблях. Это достигает нижней границы h+⌈vmax(0,l−uh)⌉. В таблице сгруппированы одинаковые загрузки и указано количество кораблей каждого вида.
T=((0;1;1);(0;5;2);(1;1;11))
Шаг 3. Да. Приведённая конструкция удовлетворяет условию.
Шаг 1. Два тяжёлых контейнера не помещаются на один корабль, поэтому для h тяжёлых контейнеров нужно не меньше h кораблей. Рядом с одним тяжёлым помещается не больше u=⌊LC−H⌋ лёгких, а на корабле без тяжёлых - не больше v=⌊LC⌋ лёгких. Значит, при m кораблях лёгких не больше uh+v(m−h).
H=7
L=2
C=10
x=11
y=17
Шаг 2. На каждый из h кораблей кладём один тяжёлый и, пока они есть, до u лёгких контейнеров. Оставшиеся лёгкие распределяем по v штук на дополнительных кораблях. Это достигает нижней границы h+⌈vmax(0,l−uh)⌉. В таблице сгруппированы одинаковые загрузки и указано количество кораблей каждого вида.
T=((0;1;1);(0;5;1);(1;1;11))
Шаг 3. Нет. Необходимая граница или полная конечная область исключает этот случай.
Шаг 1. Два тяжёлых контейнера не помещаются на один корабль, поэтому для h тяжёлых контейнеров нужно не меньше h кораблей. Рядом с одним тяжёлым помещается не больше u=⌊LC−H⌋ лёгких, а на корабле без тяжёлых - не больше v=⌊LC⌋ лёгких. Значит, при m кораблях лёгких не больше uh+v(m−h).
H=7
L=2
C=10
x=11
y=77
Шаг 2. На каждый из h кораблей кладём один тяжёлый и, пока они есть, до u лёгких контейнеров. Оставшиеся лёгкие распределяем по v штук на дополнительных кораблях. Это достигает нижней границы h+⌈vmax(0,l−uh)⌉. В таблице сгруппированы одинаковые загрузки и указано количество кораблей каждого вида.