1 / 0 / 0
Регистрация: 22.07.2014
Сообщений: 8
|
|
1 | |
Как максимально можно наполнить сосуд V с помощью маленьких сосудов?04.08.2014, 00:38. Показов 1181. Ответов 16
Метки нет (Все метки)
Есть большой сосуд вместимостью V литров. Есть N маленьких сосудов вместимостью а1, а2, ..., аN литров. Как максимально можно наполнить сосуд V с помощью маленьких сосудов. (Учитывая то, что зачерпывать маленькие сосуды нужно полностью) (V <= 10000, N <= 500, ai <= 10000)
Не могу понять как это можно решить, может у кого-то будут какие-нибудь идеи?
0
|
04.08.2014, 00:38 | |
Ответы с готовыми решениями:
16
Как можно быстро наполнить данными справочник географических названий? Сосуд разделен подвижным поршнем. В каком отношении поршень будет делить сосуд, если его меньшую часть нагреть? Установить, можно ли перелить воду из банки в один из указанных сосудов Как можно в памяти уместить больше данных ?Большой массив или список маленьких массивов ? |
2509 / 1130 / 582
Регистрация: 07.06.2014
Сообщений: 3,286
|
|
04.08.2014, 11:46 | 2 |
мысли вслух...
я бы предложил решение перебором - нахождение MAX( подсумм (a1... an)<=V) Но N может быть 500, это очень много, поэтому, я не уверен, что решение перебором пройдёт по времени...
1
|
1 / 0 / 0
Регистрация: 22.07.2014
Сообщений: 8
|
|
04.08.2014, 16:12 [ТС] | 3 |
Sergio Leone, маленькие сосуды можно использовать много раз, а ограничение по времени 2 секунды
0
|
0 / 0 / 0
Регистрация: 04.08.2014
Сообщений: 5
|
||||||
05.08.2014, 12:42 | 4 | |||||
Не совсем понятно условие..
Если гарантированно можно заполнить сосуд, то один из вариантов может быть таков.. (только ловить правильную последовательность и выходить)
0
|
2509 / 1130 / 582
Регистрация: 07.06.2014
Сообщений: 3,286
|
|
05.08.2014, 13:05 | 5 |
угу. на мой взгляд, именно 9
Добавлено через 57 секунд Не по теме: Раут, подскажите, это ваше решение через динамическое программирование, я правильно понял?
1
|
0 / 0 / 0
Регистрация: 04.08.2014
Сообщений: 5
|
|
05.08.2014, 13:17 | 6 |
Нет. Мое решение - это полный перебор. Массив s исключительно для вывода ответа.
0
|
2509 / 1130 / 582
Регистрация: 07.06.2014
Сообщений: 3,286
|
|
05.08.2014, 13:26 | 7 |
ясно. спасибо за ответ.
Думаете, что полный перебор пройдёт по времени при большом N ? и, кстати, при нахождении решения, когда сумма точно даёт V, перебор нужно прерывать, иначе ваш код продолжает искать ВСЕ возможные варианты: рекурсия есть рекурсия...
1
|
0 / 0 / 0
Регистрация: 04.08.2014
Сообщений: 5
|
|
05.08.2014, 13:34 | 8 |
Проблема не в N.. а в самих a[i].. Если они очень малы, то задача решается очень быстро.. Иначе будут проблемы.. Естественно такое решение не пройдет..
0
|
1 / 0 / 0
Регистрация: 22.07.2014
Сообщений: 8
|
|
05.08.2014, 13:40 [ТС] | 9 |
Раут, да, при вашем тесте будет такой ответ, а например при 10 3 8 7 3 будет ответ 10
0
|
Почетный модератор
64300 / 47595 / 32743
Регистрация: 18.05.2008
Сообщений: 115,181
|
|
05.08.2014, 13:51 | 10 |
0
|
0 / 0 / 0
Регистрация: 04.08.2014
Сообщений: 5
|
|
05.08.2014, 13:55 | 11 |
Puporev, все просто
0
|
1 / 0 / 0
Регистрация: 22.07.2014
Сообщений: 8
|
|
05.08.2014, 13:56 [ТС] | 12 |
Puporev, ну у вас большой сосуд вместимостью 10 и 3 маленьких вместимостями 8, 7 и 3. Т.е. в большой можно влить 7 и 3
0
|
0 / 0 / 0
Регистрация: 04.08.2014
Сообщений: 5
|
|
05.08.2014, 14:20 | 13 |
Evil Nigga, а откуда задача? Есть ли он на каком-нить ресурсе с тестирующей системой?
ИМХО, задачу нельзя решить динамическим программированием.. Поэтому только полный перебор..
0
|
266 / 192 / 50
Регистрация: 16.06.2014
Сообщений: 424
|
|
27.08.2014, 23:26 | 14 |
А разве это не рюкзак? ДП
2
|
2509 / 1130 / 582
Регистрация: 07.06.2014
Сообщений: 3,286
|
|
28.08.2014, 09:00 | 15 |
что-то мне это ДП не даётся... Кроме задач с черепашкой, другие как-то в голове не укладываются...
Iriini, если Вам не сложно, можете рассказать про алгоритм решения данной задачи через Динамическое Программирование ? Какую функцию построить, как хранить... Ну или, если Вам проще - пример программы (можно даже не рабочий, но с комментами). Заранее большое спасибо!
0
|
266 / 192 / 50
Регистрация: 16.06.2014
Сообщений: 424
|
|
28.08.2014, 16:57 | 16 |
Sergio Leone, мне нравятся разборы ИТМО
http://neerc.ifmo.ru/wiki/inde... 0%BA%D0%B5 Над этой конкретно задачей с точки зрения рюкзака надо еще подумать
2
|
191 / 161 / 116
Регистрация: 14.09.2013
Сообщений: 302
|
||||||
28.08.2014, 23:55 | 17 | |||||
1
|
28.08.2014, 23:55 | |
28.08.2014, 23:55 | |
Помогаю со студенческими работами здесь
17
Как можно оптимизировать ASP максимально? Найти количество коробочек, которые можно наполнить теми цифрами по 5 шт Как определять, сколько максимально потоков можно запускать? Не работает вся оперативка и как можно максимально ускорить данный ПК Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |