Форум программистов
 
Контакты: о проблемах с регистрацией, почтой и по другим вопросам пишите сюда - alarforum@yandex.ru, проверяйте папку спам! Обязательно пройдите активизацию e-mail.

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

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

Ответ
 
Опции темы
Старый 23.09.2018, 15:32   #1
Llirik
Пользователь
 
Регистрация: 17.05.2007
Сообщений: 15
Репутация: 10
По умолчанию Интересная задачка: разлить бочки с водой по вёдрам за минимальное число операций

Есть 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, 21:25   #2
ViktorR
Профессионал
 
Регистрация: 23.10.2010
Сообщений: 1,178
Репутация: 603
По умолчанию

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

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

Последний раз редактировалось ViktorR; 24.09.2018 в 21:31.
ViktorR вне форума   Ответить с цитированием
Старый 25.09.2018, 10:35   #3
evg_m
Профессионал
 
Регистрация: 20.04.2008
Сообщений: 4,753
Репутация: 2097
По умолчанию

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

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

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

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

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

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

Цитата:
только последнее ведро, в которое попадет вода может быть не полным
ведро =10 л
все бочки по 3 литра и их(таких бочек) N>3 (после наливания полных 10 литровых ведер)
оптимально 3+3+3 =9 <10 причем N/3 >1 таких ведер
и только в случае если мы ЗНАЕМ что не хватит места (ведер) надо доливать ведра до полной(разливать 3 литра бочки на разные ведра)
3+3+3+1 =10
__________________
программа — запись алгоритма на языке понятном транслятору

Последний раз редактировалось evg_m; 25.09.2018 в 11:59.
evg_m вне форума   Ответить с цитированием
Старый 25.09.2018, 12:22   #6
Llirik
Пользователь
 
Регистрация: 17.05.2007
Сообщений: 15
Репутация: 10
По умолчанию

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


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

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

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

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

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

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

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

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

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

Опции темы

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.

Быстрый переход

Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Интересная задачка Yeleo1 Помощь студентам 3 03.04.2015 21:59
Число фибоначчи. Двумерный массив, максимальное и минимальное число. Silverstone Assembler 0 02.12.2012 12:19
Интересная задачка stscolt Помощь студентам 1 29.04.2008 08:06


18:16.


Powered by vBulletin® Version 3.8.8 Beta 2
Copyright ©2000 - 2018, Jelsoft Enterprises Ltd.

RusProfile.ru


Справочник российских юридических лиц и организаций.
Проекты отопления, пеллетные котлы, бойлеры, радиаторы
интернет магазин respective.ru