Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > Delphi программирование > Паскаль, Turbo Pascal, PascalABC.NET
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 23.09.2018, 14:32   #1
Llirik
Пользователь
 
Регистрация: 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;

У кого какие мысли по алгоритму?!
Llirik вне форума Ответить с цитированием
Старый 24.09.2018, 20:25   #2
ViktorR
Старожил
 
Регистрация: 23.10.2010
Сообщений: 2,304
По умолчанию

Цитата:
При этом в каждом последующем ведре объем воды не должен превышать объем в предыдущем ведре (необходимо каждое текущее ведро заливать максимально возможно).
Не факт, что ведро надо заливать по максимуму.
Объём воды в бочках может быть меньше объёма воды, требуемого для заливки вёдер "под завязку".
Важно только то, что в следующем ведре воды должно быть столько, сколько в предыдущем или менее.
Например, все вёдра можно залить наполовину, а последнее на 1/3 или просто капнуть в него .
Так понимаю, что во все M вёдер надо налить воды, а сколько ???
Можно взять одну бочку и налить воду во все вёдра в соответствии с условием. Поскольку число переливов >= M то такое решение будет оптимальным, поскольку число переливов будет равно M.

На мой взгляд задача не до конца определена, что-то не хватает.
Может быть часть условия, помещённая в круглые скобки и читаемая как пояснение, должна быть самостоятельной частью условия?
Все вёдра заливать по полной и, возможно, несколько последних вёдер залить частично?
Обязательно ли трогать все бочки? Воды в бочках может быть больше чем необходимо для заливки в вёдра ...
Как-то так, ...

Последний раз редактировалось ViktorR; 24.09.2018 в 20:31.
ViktorR вне форума Ответить с цитированием
Старый 25.09.2018, 09:35   #3
evg_m
Старожил
 
Регистрация: 20.04.2008
Сообщений: 5,515
По умолчанию

Цитата:
На мой взгляд задача не до конца определена, что-то не хватает.
Цитата:
затратив минимальное количество операций переливаний.
т.е. выгоднее с т.з. условий задачи
вылить из бочки в ОДНО новое ведро оставив предыдущеее неполным (одно переливание)
чем долить текущее и начать наполнять новое(два переливания)
Да вот оставленное неполным ведро начинает ограничивать всю дальнейшую работу
Цитата:
объем воды не должен превышать объем в предыдущем ведре
1. наполняем полные ведра из каждой одной бочки пока это возможно.
теперь в каждой бочке <V0 литров (остаток)
2. если можно наполняем полное ведро из нескольких и выливая их при этом до конца
это минимально возможные и необходимые переливания

3. а теперь начнется самое интересное и непонятное.
для получения полных ведер нам потребуется
- разливать остаток бочки в разные ведра (см. выше )
- НО ведь можно оставить ведро и неполным начиная с наиболее наполненных(или комбинации нескольких) бочек (это оптимально, НО вдруг нам не хватит ли ведер?)
Цитата:
Есть M пустых ведер
если разливать бочкИ по разным ведрам до наполнения то по сути нам все равно сколько бочек мы будем делить, главное что учитывается на сколько ведер мы ее разделим.

желательно (если не необходимо) наливать из бочки ровно в одно ведро (после выполнения п.1.) и наполняя при этом ведра как можно полнее.
программа — запись алгоритма на языке понятном транслятору
evg_m на форуме Ответить с цитированием
Старый 25.09.2018, 09:44   #4
Аватар
Старожил
 
Аватар для Аватар
 
Регистрация: 17.11.2010
Сообщений: 19,042
По умолчанию

Цитата:
НО ведь можно оставить ведро и неполным начиная с наиболее наполненных(или комбинации нескольких) бочек (это оптимально, НО вдруг нам не хватит ли ведер?)
Судя по этому
Цитата:
необходимо каждое текущее ведро заливать максимально возможно
только последнее ведро, в которое попадет вода может быть не полным

Разливка остатка воды в бочках напоминает задачу об оптимальной укладке разных коробок в контейнеры
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию

Последний раз редактировалось Аватар; 25.09.2018 в 09:47.
Аватар вне форума Ответить с цитированием
Старый 25.09.2018, 10:53   #5
evg_m
Старожил
 
Регистрация: 20.04.2008
Сообщений: 5,515
По умолчанию

Цитата:
только последнее ведро, в которое попадет вода может быть не полным
ведро =10 л
все бочки по 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.
evg_m на форуме Ответить с цитированием
Старый 25.09.2018, 11:22   #6
Llirik
Пользователь
 
Регистрация: 17.05.2007
Сообщений: 15
По умолчанию

Цитата:
Сообщение от evg_m Посмотреть сообщение
1. наполняем полные ведра из каждой одной бочки пока это возможно.
теперь в каждой бочке <V0 литров (остаток)
Я также подумал. Т.е. " обрезаем" все бочки до уровня меньшего V0.
Единственно только вопрос. А не возникнет ли ситуация, когда выгоднее разделить последние 2*V0 по другому? Например, 11 литров разделить не на 10+1, а на 7+4...


Цитата:
Сообщение от evg_m Посмотреть сообщение
и только в случае если мы ЗНАЕМ что не хватит места (ведер) надо доливать ведра до полной(разливать 3 литра бочки на разные ведра)
Вот вот! Если в ведрах не ограничиваться, то решение простое.
Сначала отливаем из бочек у которых объем больше V0, пока не останется остатки <V0.
А потом рекурсией комбинируем остатки так, чтобы найти комбинацию с максимальным заполнением - это очередное ведро. И так несколько итераций, пока остатков не останется.

Но такой финт работает если ведер много. А если мы ограничены в их количестве? В этом и интересность... )))
Llirik вне форума Ответить с цитированием
Старый 25.09.2018, 11:41   #7
Llirik
Пользователь
 
Регистрация: 17.05.2007
Сообщений: 15
По умолчанию

Еще уточнения по условиям:
Требование выполнить минимальное количество переливаний - приорететное!

Требование по максимально возможному (при минимальном количестве переливаний) заполнению продиктовано лишь тем, чтобы уйти от бесконечных вариантов.

Поясню:
15 литров можно разлить в 2 ведра (двумя переливаниями) бесконечо большим количеством способов. Например: 10+5, 9.99+5.01 т.п... Чтобы не создавать такую вольную неопределенность и введено условие пытаться наливать по максимуму.

Требование не увеличения объема следующего ведра на самом-то деле ничтожное, т.к. его можно выполнить после разлива простой сортировкой по убыванию...
)))
Llirik вне форума Ответить с цитированием
Старый 25.09.2018, 11:54   #8
Аватар
Старожил
 
Аватар для Аватар
 
Регистрация: 17.11.2010
Сообщений: 19,042
По умолчанию

Цитата:
Требование по максимально возможному (при минимальном количестве переливаний) заполнению продиктовано лишь тем, чтобы уйти от бесконечных вариантов.
Если оно не обязательно, зачем тогда в условии? А от бесконечных вариантов спасет условие оптимальности )
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
Аватар вне форума Ответить с цитированием
Старый 25.09.2018, 12:29   #9
Llirik
Пользователь
 
Регистрация: 17.05.2007
Сообщений: 15
По умолчанию

Цитата:
Сообщение от Аватар Посмотреть сообщение
Если оно не обязательно, зачем тогда в условии? А от бесконечных вариантов спасет условие оптимальности )
))) Убрать одно условие, чтобы добавить другое?
И как оно должно звучать не повторяя смысловую нагрузку первоначального условия?
)))
Llirik вне форума Ответить с цитированием
Старый 25.09.2018, 12:32   #10
Аватар
Старожил
 
Аватар для Аватар
 
Регистрация: 17.11.2010
Сообщений: 19,042
По умолчанию

Цитата:
Убрать одно условие, чтобы добавить другое?
Так есть же
Цитата:
затратив минимальное количество операций переливаний
А количество оптимальных решений не одно в любом случае, диофантова же система линейных уравнений с кучей неизвестных )
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
Аватар вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Интересная задачка 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