| Вопрос: Задачка | Добавлено: 17.04.05 15:57 |
Автор вопроса:  Sharp | Web-сайт: sharpc.livejournal.com | ICQ: 216865379 |
|
Имеется N книг с толщинами W[N] и полка длиной L. Требуется определить, какие книги надо поставить на полку, чтобы оставалось как можно меньше свободного места.
Пример: N=6; L=200 W[] = {100, 50, 29, 25, 24, 19} Ответ: 1, 2, 4, 5 |
| Ответы | Всего ответов: 17 |
|
Номер ответа: 1 Автор ответа:  Morpheus Вопросов: 224 Ответов: 3777 |
Web-сайт: Профиль | | #1 | Добавлено: 17.04.05 16:31 |
А какое ограничение на количество книг? я спрашиваю так как можно использовать грубую силу перебора вариантов, а если много то соответственно нельзя. Как по мне дык без перебора (или может быть рекурсии, но тут я не уверен) не обойтись 
|
||
|
Номер ответа: 2 Автор ответа: sneРазработчик Offline Client ICQ: 233286456 Вопросов: 34 Ответов: 5445 |
Web-сайт: Профиль | | #2 | Добавлено: 17.04.05 18:57 |
| Дык перебором и искать, и на скорость это особо не повлияет, пусть их даже сотни будут... | ||
|
Номер ответа: 3 Автор ответа: MorpheusВопросов: 224 Ответов: 3777 |
Web-сайт: Профиль | | #3 | Добавлено: 17.04.05 19:23 |
Просто опыт олимпиад показывает что если у задачи (такой как эта) есть очевидное решение будь там хоть сотни книг, обязательно напишут что книг будет до 100 тысяч 
|
||
|
Номер ответа: 4 Автор ответа: SharpЛидер форума ICQ: 216865379 Вопросов: 106 Ответов: 9979 |
Web-сайт: Профиль | | #4 | Добавлено: 17.04.05 21:11 |
| Допустим, L, N<1000 | ||
|
Номер ответа: 5 Автор ответа: MorpheusВопросов: 224 Ответов: 3777 |
Web-сайт: Профиль | | #5 | Добавлено: 17.04.05 23:47 |
|
2Sharp
Не сочтёшь за личное оскорбление если код будет на паскале? (пока нет никакого) |
||
|
Номер ответа: 6 Автор ответа: SharpЛидер форума ICQ: 216865379 Вопросов: 106 Ответов: 9979 |
Web-сайт: Профиль | | #6 | Добавлено: 18.04.05 00:01 |
| Лучше на С++ или на VB | ||
|
Номер ответа: 7 Автор ответа: MorpheusВопросов: 224 Ответов: 3777 |
Web-сайт: Профиль | | #7 | Добавлено: 18.04.05 00:09 |
|
На вб я ленюсь такое делать так как не знаю каким способом (кроме мида или сплита) выдрать последовательность чисел из тексбокса а си щас не установлен. попробую пока так
|
||
|
Номер ответа: 8 Автор ответа: SharpЛидер форума ICQ: 216865379 Вопросов: 106 Ответов: 9979 |
Web-сайт: Профиль | | #8 | Добавлено: 18.04.05 01:26 |
| Чем тебя не устраивает mid или split? И вообще можно исходные данные писать в коде, главное - алгоритм | ||
|
Номер ответа: 9 Автор ответа: MorpheusВопросов: 224 Ответов: 3777 |
Web-сайт: Профиль | | #9 | Добавлено: 18.04.05 01:30 |
|
Sharp
Потом мож переведу напаскале тяжелее тк я хотел создать матрицу 1000х1000 а паскаль не дал, типа большой очень. я так подумал и решил что он нафиш не нужен. а в ВБ бы до сих пор бы парился
Уффф... с рекурсией тяжеловато, вроде чё-то выдаёт, но баги лезут. |
||
|
Номер ответа: 10 Автор ответа: SharpЛидер форума ICQ: 216865379 Вопросов: 106 Ответов: 9979 |
Web-сайт: Профиль | | #10 | Добавлено: 18.04.05 01:32 |
| Есть намного более быстрый вариант решения без рекурсии | ||
|
Номер ответа: 11 Автор ответа: crestaВопросов: 117 Ответов: 1538 |
Профиль | | #11 | Добавлено: 18.04.05 02:00 |
|
Ну минимальное количество книг - это три. Максимальное - шесть.
Делаем "маски" размером от 3 до 0. Примерно такие: {X,0,0,X,X,0} и накладываем на исходный массив и получаем {100,0,0,25,24,0}. Суммируем и запоминаем как максимально подходящее значение. Перебираем последовательно все возможные маски, сравнивая с максимальным значением получающиеся суммы. И получаем в конце максимальную комбинацию. Применение маски исключает львиную долю проверок (исключается проверка для масок размером 4-5-6 элементов). И без рекурсии. |
||
|
Номер ответа: 12 Автор ответа: MorpheusВопросов: 224 Ответов: 3777 |
Web-сайт: Профиль | | #12 | Добавлено: 18.04.05 02:25 |
|
Классный метод! Можно по подробнее, я просто н понял-откуда три и откуда 6 И как генер. маски - все все все возможные? (хотя их не так и много наверное)
|
||
|
Номер ответа: 13 Автор ответа: SharpЛидер форума ICQ: 216865379 Вопросов: 106 Ответов: 9979 |
Web-сайт: Профиль | | #13 | Добавлено: 18.04.05 03:59 |
| А представь себе маску размером 500 :P Боюсь, их будет очень много | ||
|
Номер ответа: 14 Автор ответа: MorpheusВопросов: 224 Ответов: 3777 |
Web-сайт: Профиль | | #14 | Добавлено: 18.04.05 04:35 |
| Всё таки моя прога работает наполовину, там где то скрытый баг что иногда она ошибается (не учитывает если расстояние (свободное место)=0) хотя вроде везде указал | ||
|
Номер ответа: 15 Автор ответа: crestaВопросов: 117 Ответов: 1538 |
Профиль | | #15 | Добавлено: 18.04.05 17:52 |
|
Откуда 3?
100+50+29=179. Если +25 уже перебор. Среди оставшихся книг может не оказаться необходимой с толщиной 21. Откуда 6? 19+24+25+29+50=147 Если +100, то опять перебор. Не знаю, почему, но кажется (на уровне интуиции) что должно быть получившиеся 5 +1. Sharp тут не в том дело, 500 или 6, это способ исключить часть непроизводительных проверок. И чем больше книг, тем больший эффект будет от такого способа. Например для 20 книг 50,47,41,38,35,33,32,29,21,15,14,13,11,10,8,6,5,4,3,1 Правильное решение лежит в диапазоне 4-15 книг. Исключаются 1,2,3-книжные комбинации, и что самое приятное, самые тяжелые случаи- 20,19,18,17,16-книжные комбинации. Ну конечно это не алгоритм решения, просто способ исключить львиную долю проверок в случае избрания алгоритма прямого перебора. |
||