|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
|
Опции темы | Поиск в этой теме |
23.09.2018, 14:32 | #1 |
Пользователь
Регистрация: 17.05.2007
Сообщений: 15
|
Интересная задачка: разлить бочки с водой по вёдрам за минимальное число операций
Есть N бочек с водой. Бочки могут иметь различный объем.
Есть M пустых ведер с фиксированным объемом V0 (пусть будет константа V0=10). Из одной бочки можно переливать воду в разные ведра. В одно ведро можно наливать воду из разных бочек. Необходимо перелить воду в ведра, затратив минимальное количество операций переливаний. При этом в каждом последующем ведре объем воды не должен превышать объем в предыдущем ведре (необходимо каждое текущее ведро заливать максимально возможно). Пусть массив V[1..N] - это объемы бочек. Решаем исходя из M*V0 не меньше суммы всех V[i] (это отдельная обработка). Необходимо сформировать массив А[1..N,1..M] такой, что А[i,j] - это объем воды перелитой из i-той бочки в j-тое ведро, такой, чтобы количество ненулевых элементов было минимальным. . Пример1: N:=2; V[1]:=5; V[2]:=4; M:=2; Единственное верное решение: A[1,1]:=5; A[1,2]:=0; A[2,1]:=4; A[1,2]:=0; Пример2: N:=2; V[1]:=7; V[2]:=6; M:=2; Два верных решения: 1) A[1,1]:=7; A[1,2]:=0; A[2,1]:=3; A[1,2]:=3; 2) A[1,1]:=4; A[1,2]:=3; A[2,1]:=6; A[1,2]:=0; У кого какие мысли по алгоритму?! |
24.09.2018, 20:25 | #2 | |
Старожил
Регистрация: 23.10.2010
Сообщений: 2,330
|
Цитата:
Объём воды в бочках может быть меньше объёма воды, требуемого для заливки вёдер "под завязку". Важно только то, что в следующем ведре воды должно быть столько, сколько в предыдущем или менее. Например, все вёдра можно залить наполовину, а последнее на 1/3 или просто капнуть в него . Так понимаю, что во все M вёдер надо налить воды, а сколько ??? Можно взять одну бочку и налить воду во все вёдра в соответствии с условием. Поскольку число переливов >= M то такое решение будет оптимальным, поскольку число переливов будет равно M. На мой взгляд задача не до конца определена, что-то не хватает. Может быть часть условия, помещённая в круглые скобки и читаемая как пояснение, должна быть самостоятельной частью условия? Все вёдра заливать по полной и, возможно, несколько последних вёдер залить частично? Обязательно ли трогать все бочки? Воды в бочках может быть больше чем необходимо для заливки в вёдра ...
Как-то так, ...
Последний раз редактировалось ViktorR; 24.09.2018 в 20:31. |
|
25.09.2018, 09:35 | #3 | ||||
Старожил
Регистрация: 20.04.2008
Сообщений: 5,528
|
Цитата:
Цитата:
вылить из бочки в ОДНО новое ведро оставив предыдущеее неполным (одно переливание) чем долить текущее и начать наполнять новое(два переливания) Да вот оставленное неполным ведро начинает ограничивать всю дальнейшую работу Цитата:
теперь в каждой бочке <V0 литров (остаток) 2. если можно наполняем полное ведро из нескольких и выливая их при этом до конца это минимально возможные и необходимые переливания 3. а теперь начнется самое интересное и непонятное. для получения полных ведер нам потребуется - разливать остаток бочки в разные ведра (см. выше ) - НО ведь можно оставить ведро и неполным начиная с наиболее наполненных(или комбинации нескольких) бочек (это оптимально, НО вдруг нам не хватит ли ведер?) Цитата:
желательно (если не необходимо) наливать из бочки ровно в одно ведро (после выполнения п.1.) и наполняя при этом ведра как можно полнее.
программа — запись алгоритма на языке понятном транслятору
|
||||
25.09.2018, 09:44 | #4 | ||
Старожил
Регистрация: 17.11.2010
Сообщений: 18,922
|
Цитата:
Цитата:
Разливка остатка воды в бочках напоминает задачу об оптимальной укладке разных коробок в контейнеры
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
Последний раз редактировалось Аватар; 25.09.2018 в 09:47. |
||
25.09.2018, 10:53 | #5 | |
Старожил
Регистрация: 20.04.2008
Сообщений: 5,528
|
Цитата:
все бочки по 3 литра и их(таких бочек) N>3 (после наливания полных 10 литровых ведер) оптимально 3+3+3 =9 <10 причем N/3 >1 таких ведер и только в случае если мы ЗНАЕМ что не хватит места (ведер) надо доливать ведра до полной(разливать 3 литра бочки на разные ведра) 3+3+3+1 =10
программа — запись алгоритма на языке понятном транслятору
Последний раз редактировалось evg_m; 25.09.2018 в 10:59. |
|
25.09.2018, 11:22 | #6 | ||
Пользователь
Регистрация: 17.05.2007
Сообщений: 15
|
Цитата:
Единственно только вопрос. А не возникнет ли ситуация, когда выгоднее разделить последние 2*V0 по другому? Например, 11 литров разделить не на 10+1, а на 7+4... Цитата:
Сначала отливаем из бочек у которых объем больше V0, пока не останется остатки <V0. А потом рекурсией комбинируем остатки так, чтобы найти комбинацию с максимальным заполнением - это очередное ведро. И так несколько итераций, пока остатков не останется. Но такой финт работает если ведер много. А если мы ограничены в их количестве? В этом и интересность... ))) |
||
25.09.2018, 11:41 | #7 |
Пользователь
Регистрация: 17.05.2007
Сообщений: 15
|
Еще уточнения по условиям:
Требование выполнить минимальное количество переливаний - приорететное! Требование по максимально возможному (при минимальном количестве переливаний) заполнению продиктовано лишь тем, чтобы уйти от бесконечных вариантов. Поясню: 15 литров можно разлить в 2 ведра (двумя переливаниями) бесконечо большим количеством способов. Например: 10+5, 9.99+5.01 т.п... Чтобы не создавать такую вольную неопределенность и введено условие пытаться наливать по максимуму. Требование не увеличения объема следующего ведра на самом-то деле ничтожное, т.к. его можно выполнить после разлива простой сортировкой по убыванию... ))) |
25.09.2018, 11:54 | #8 | |
Старожил
Регистрация: 17.11.2010
Сообщений: 18,922
|
Цитата:
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
|
|
25.09.2018, 12:29 | #9 |
Пользователь
Регистрация: 17.05.2007
Сообщений: 15
|
|
25.09.2018, 12:32 | #10 | ||
Старожил
Регистрация: 17.11.2010
Сообщений: 18,922
|
Цитата:
Цитата:
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
|
||
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Интересная задачка | Yeleo1 | Помощь студентам | 3 | 03.04.2015 20:59 |
Число фибоначчи. Двумерный массив, максимальное и минимальное число. | Silverstone | Assembler - Ассемблер (FASM, MASM, WASM, NASM, GoASM, Gas, RosAsm, HLA) и не рекомендуем TASM | 0 | 02.12.2012 12:19 |
Интересная задачка | stscolt | Помощь студентам | 1 | 29.04.2008 08:06 |