В общем, универсальный алгоритм я грубо написал выше. Немного обдумал во сне и вывел окончательно, с учетом всяких вариантов. Если интересно, распишу даром, но вечером. Как я и думал, ничего сложного, это не шахматы и даже не шашки.
В моем алгоритме как раз и выделяется место под самого худого, который и будет доутрамбовывать пачку. У меня не получается придумать случай, когда самому легкому 1 раз НЕ нужно плыть (исключая случаи когда плавают одни толстые или самых худых больше 2). Там где может плавать НеСамыйХудой являясь паромщиком, может плавать и СамыйХудой, что не изменит скорость переплывания всех. Может Вы подсознательно жалеете самого худого и хотите ввести параметр "усталость"?
Попробую объяснить. 1. Проверяем, есть ли в команде как минимум двое, которые помещаются в одну лодку. Без этого задача не имеет решения. 2. Далее алгоритм делится на два: загрузка лодки "туда" (сложнее) и "обратно" (проще). Туда: 1. Сортируем по весу. Берем самого легкого, сажаем в лодку. Смотрим можно ли посадить с ним кого-то еще. 2. Если можем, то сажаем второго, третьего и так далее, сколько влезет по весу. 3. Если не можем, то есть со вторым перевес, высаживаем легкого, отправляем одного тяжелого. Это получится минимум на третьем ходе. Обратно: 1. Плывет самый легкий один. И так в цикле, пока не уплывут двое последних. Все. Схема работает на любом количестве и прочих условиях, даже вычурных. Например, лодка 100, чуваки 90, 80, 70, 40, 30.
Ок, примем, что схема рабочая. Где доказательство, что найденное решение - оптимальное? Лодка грузоподъёмностью в 150 кг, и 100 человек разных масс - гулять, так гулять
Прошу понять правильно: отсутствие лишних и повторяющихся движений - не является доказательством того, что найденное решение - оптимальное. Вот расклад по вашему алгоритму при вводных: грузоподъёмность лодки - 10, кол-во человек - 8, заранее отсортированы по весу, переправой считается любое переплытие речки: На старте: 1,2,3,4,5,6,7,8 => 1,2,3,4 = загрузка 10 <= 1 1,5,6,7,8 - остались => 1,5 = загрузка 6, начинаем терять в полезной к переправе массе <= 1 1,6,7,8 - остались => 1,6 = 7 - и тут теряем <= 1 1,7,8 - остались => 1,7 = 8, ещё пару кг потерли <= 1 1,8 - остались => 1,8 - килограмм потери. Итого - 9 переправ. Потери массы - 10 кг, одна полная загрузка лодки! А ниже - более оптимальное решение, из 7 переправ: На старте: 1,2,3,4,5,6,7,8 => 1,8 - потеря 1 кг <= 1 1,2,3,4,5,6,7 => 1,2,7 - без потерь <= 1 1,3,4,5,6 => 1,3,6 - без потерь <= 1 1,4,5 - без потерь => 1,4,5 7 переправ, потеря массы - 1 кг, на 2 переправы меньше, или на 23% эффективнее решения по вашему алгоритму. Ваш алгоритм - не даёт доказанного оптимального решения. И да - комбинаторика тут при чём, как видите Я не зря упоминал задачу про ранец. Как видите, решение, где первым ходом является не самый оптимальный, т.к.потеря массы имеет место быть - далее лидирует без потерь массы вообще, в отличие от первого решения, где первый ход - без потерь массы, зато потом - происходит полная деградация эффективности алгоритма.
Исходя из вышеизложенного: нам требуется математическое обоснование следующего утверждения: доказать, что предпринятая на i-том шаге итерации компоновка загрузки лодки по-максимуму - не приведёт к деградации эффективности алгоритма на дальнейших шагах, вплоть до последнего шага.
Старт 1 2 3 4 5 6 7 8 => 2 и 8 = 10 <= 2 осталось 1 2 3 4 5 6 7 => 1 2 7 = 10 <= 1 осталось 1 3 4 5 6 => 1 3 6 = 10 <= 1 осталось 1 4 5 = 10 => всех (игрался с цифрами и только сейчас заметил, что я просто повторил предложенный выше вариант, только 1 ход изменил) Спойлер: лажа если брать самого толстого и ближайшего до 10 легкого Старт 1 2 3 4 5 6 7 8 => 2 и 8 = 10 <= 2 осталось 1 2 3 4 5 6 7 => 3 7 = 10 <= 3 осталось 1 2 3 4 5 6 => 4 6 = 10 <= 4 осталось 1 2 3 5 = 10 => 2, 3 и 5 <= 2 осталось 1 и 2 => всех кпд лодки 100%) есть отклонение от моего алгоритма - на первом шаге попробовал пустить не самого легкого паромщиком, но сути это не меняет. Но у меня есть аналогичная проблема. При выборе пачки у меня нет разницы между <2 и 8> и <1, 2, 3 и 4> (я предполагал рандомно выбирать из 2-х пачек). Масса обоих равна 10, но переправа 2-й пачки приведет к увеличению количества перегонов. Можно обратить внимание, что я сейчас брал самого толстого из оставшихся и доукомплектовывал до полной лодки легкими. Причем тупо брать 8 и 2 или 7 и 3 не выгодно. Наверное, смысла назначать паромщика нет. Зато можно модернизировать алгоритм выбора пачки. Там должен быть самый толстый и набор (сочетания) легких, чтобы масса доходила до М. Перебор легких начинается с самого начала. Хотя, может, и сочетания не нужны? Просто откусывать от кучи слева и справа?
Ну шо - не самая лёгкая задача, да? Вы уже нашли более оптимальное решение (хотя и оно может быть спорным, например, при перевозке на Марс - самый лёгкий кушает меньше, следовательно, более предпочтительна потеря в эффективности в одну единицу загрузки, чем гонять номер 2 на первом ходу туда-сюда ) - хоть ходов также 7, но потерь по загрузке лодки "туда" - нету. Об этом, в частности, я и вёл речь, когда говорил, что нюансов - хватает. Комбинаторика и анализ развития ситуации Может, и сочетания не нужны. Может, просто откусывать от кучи слева и справа. Может - ещё как. Главное - не это, а доказать, что найденное решение, среди кучи других решений - оптимальное. Ведь в этом весь и смысл, т.к. тупо в лоб задачу решить - очень просто, что и продемонстрировал @ostrov. З.Ы. А если представить, что человек - 1000 особей, причём их условные веса распределены несколькими способами: случайным, групповым (когда есть группы с одинаковым весом)? Сколько вариантов комбинаций будет? Какое из найденных решений будет оптимальным? Можно ли утверждать, что если на i-том шаге условная ценность выбора очередного пассажира из группы с одинаковым весом (в ситуации, когда предыдущий шаг с выбором одного человека из группы не привёл к потере эффективности - этой группе повышается приоритет выборки на следующем шаге) - то на шаге i+1 не произойдёт провал алгоритма? Ведь набор возможных эффективных комбинаций - постоянно меняется, по мере перевозки; это только кажется, что раз в начале был строго определённый набор данных, то и количество эффективных комбинаций на каждом шаге - будет неизменным. Но это - не так На самом деле - подобный класс задач имеет просто огромнейшее практическое значение, просто огромнейшее. Да и теоретическое - тоже, ведь разминать мозги всегда полезно Представьте, что стоимость одного шага перевозки (на Марс, например) составляет 100 миллионов долларов. Решать в лоб, за 9 ходов - потерять пару сотен миллионов Решивши за 7 - сэкономить эти пару сотен миллионов. Нормальный такой профит
На вики, кстати, есть статейка по теме: https://ru.wikipedia.org/wiki/Комбинаторная_оптимизация Цитаты оттуда: Ну и, чтобы было понятно, к чему хочу подвести: за решение проблемы P=NP дают миллион долларов Реальных, без дураков.
Ладно, алгоритм утрамбовывания при посадке нужен чуть сложнее. А что вы хотели за бесплатно? Возможно, просто перевернуть его, к самому тощему начинать запихивать начиная с самого толстого. Кароче, тетрис.
Уговорил таки Почему бесплатно? Миллион долларов. Задача-то сводится к решению проблемы P=NP Вон, задача коммивояжёра уже при 67 городах становится трансвычислительной. И обсуждаемая нами задача, скорее всего, при каком-то исходном количестве пассажиров - тоже. И это будет не "чуть сложнее", на секундочку.
А почему здесь все исходят из предположения, что все трое подошли к реке с одной и той же стороны? В условии этого нет.
Потому что вводные: т.е. по определению трое туристов находятся на оном берегу реки. Нефик там надумывать и жонглировать смысловым слоем, принцип бритвы Оккама.
Из процитированного как раз это следует однозначно. А ваши додумки - это типичный случай нахождения себе проблем на ровном месте. Про бритву Оккама - я не зря написал. Не зашоривайтесь, не надо оставаться настолько программистом. Если написано "должны перебраться" - это значит, что ещё не перебрались, и додумывать - не надо. Задача изначально - НЕ ПРОГРАММИСТСКАЯ, понимаете? И сделана для разминки мозгов. И никто там не парился, что однажды программист Вася начнёт кричать - не полностью формализованное ТЗ, ахтунг! С наступающим!
В данном случае зашорены как раз вы, и додумываете условия которых исходно в постановке нет. А если бы в условии было бы написано, "Двое туристов подошли к реке и должны через нее перебраться" вы бы тоже решили, что они подошли вместе? Про Оккама я в курсе , но тут он не при делах.
Я, конечно, понимаю, к чему вы клоните: сославшись на неполную формализацию ТЗ, можно поступить, как в байке про поимку льва в пустыне - сказать, что все трое уже на нужном берегу, и всё. Но - давайте не будем прикидываться дурачками, и признаем, что задача - не про мозговыверт, не про логические уловки, и её условия однозначно понятны всем, кроме, пожалуй, совсем затюканных стандартами составления ТЗ программистов. Правда ведь?
В той классике совсем другие условия задачи. Я ещё раз вам напишу: не жонглируйте без необходимости смысловым слоем. Можете открыть голосование, если хотите. И я уверен, что подавляющему большинству будут однозначно понятны условия обсуждаемой в теме задачи. Вы же - хотите всё свести к полной формализации ТЗ. Вопрос: зачем? Делать нехрен? Скучно стало, и захотелось перекорёжить задачу так, как карта ляжет? Ещё раз подчеркну: я понимаю ваши доводы, и как программисту - они мне во многом близки, но - это не тот случай, когда надо настолько занудствовать.