Помогите решить задачу.

[Diplomate 3,114]

Пожалуйста, помогите решить эту задачу.

1Нажмите здесь!

 

Вы решили заказать пиццу с доставкой на дом. Известно, что для клиентов, сделавших заказ на сумму более C рублей, доставка является бесплатной, при заказе на C рублей и меньше доставка стоит B рублей.

Вы уже выбрали товар, стоимостью A рублей. В наличии имеются еще N товаров стоимостью d1, ..., dN рублей, каждый в единственном экземпляре. Их также можно включить в заказ.

Как потратить меньше всего денег и получить на дом уже выбранный товар в A рублей?

Формат входных данных

Сначала вводятся числа A, B, C, N, а затем N чисел d1, ..., dN.

Все числа целые, 1 ≤ A ≤ 1000, 1 ≤ B ≤ 1000, 1 ≤ C ≤ 1000, 0 ≤ N ≤ 1000, 1 ≤ di ≤ 1 000 000.

Формат выходных данных

Выведите сначала суммарное количество денег, которое придется потратить. Если при этом вы планируете сделать дополнительный заказ c расчетом на бесплатную доставку, то далее выведите количество этих товаров и их номера в возрастающем порядке. Если же Вы будете оплачивать доставку сами, то далее выведите одно число –1 (минус один).

[Cкрыть]

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

P.S. На киберфоруме задавал этот вопрос, но никто не ответил. Может хоть тут кто-нибудь подскажет мне, как это сделать? В награду могу перечислить виры и проставить спасибки.

[Deceased WhiteBear 4,399]

Упорядочиваешь числа от большего к меньшему.

Выбираешь крайние.

Начинаешь двигаться с обоих сторон к центру.

Если недобор - меняешь маленькое на побольше.

Если перебор - меняешь большое на поменьше.

После каждого шага оцениваешь, соответствует условиям или нет, если да - насколько отличается от идеала.

Всё время помнить лучшее приближение.

Где-то так ИМХО.

[Diplomate 3,114]

Упорядочиваешь числа от большего к меньшему.

Выбираешь крайние.

Начинаешь двигаться с обоих сторон к центру.

Если недобор - меняешь маленькое на побольше.

Если перебор - меняешь большое на поменьше.

После каждого шага оцениваешь, соответствует условиям или нет, если да - насколько отличается от идеала.

Всё время помнить лучшее приближение.

Где-то так ИМХО.

Эм, немного не понял. Я должен использовать только два числа?

И опять же, товаров дофига. Больно долго будет все перебирать.

Изменено 10.08.2014, 18:15:29 пользователем Diplomate

[Detech 2,181]

Можно извращнуться рекурсией

Есть некая функция на вход которой подается набор элементов и число.

Для набора из 1 элемента - функция возвращает элемент если он меньше числа, или нуль если он больше числа.

Для набора из N элементов - функция возвращает

Если число меньше нуля - возвращет нуль

Если число больше нуля - возвращает максимальное из всех наборов Функция (набор без итератора, число минус итератор) + итератор

Сложность оценить не берусь доказательная база - нуль, но есть ощущение что он выдаст число максимально стремящееся к указанному снизу. Надо конечно сверху, но можно изобразить задачу от обратного - то есть находить набор элементов которые надо выложить, а не положить

То есть если из описания не понятно, то примеры:

Func({5},4) = 0 потому что единственный элемент набора больше числа

Func({5},8) = 5 потому что единственный элемент набора меньше числа

Func({5, 7}, 8) = 7, так как Func({5}, 1)+7 большее из набора (Func({5}, 1)+7, Func({7}, 3)+5)

Func({5, 2, 7}, 11) = 9

так как

Func({5, 2}, 4) = 2 + 7 = 9 (функция от 5 возвращает нуль, 2 больше нуля)

Func({5, 7}, 9) = 7 + 2 = 9 (функция от 5 возвращает 5, функция от 7 возвращает 7, 7 больше 5)

Func({2, 7}, 6) = 2 + 5 = 7 (функция от 2 возвращает 2, функция от 7 возвращает нуль, 2 больше нуля)

и т.д.

Эм, немного не понял. Я должен использовать только два числа?

И опять же, товаров дофига. Больно долго будет все перебирать.

Перебирать будет недолго, это алгоритм N сложности. Другое дело что он реально ограничен только 2 товарами, что не соотвествует условию

Изменено 10.08.2014, 18:38:47 пользователем Detech

[mr_john 1,486]

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

Изменено 10.08.2014, 18:28:31 пользователем mr_john

[MaslovRG 6,935]

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

http://informatics.mccme.ru/py-source/source/dir/351-17227

[Diplomate 3,114]

Можно извращнуться рекурсией

Есть некая функция на вход которой подается набор элементов и число.

Для набора из 1 элемента - функция возвращает элемент если он меньше числа, или нуль если он больше числа.

Для набора из N элементов - функция возвращает

Если число меньше нуля - возвращет нуль

Если число больше нуля - возвращает минимальное из всех наборов Функция (набор без итератора, число минус итератор)

Сложность оценить не берусь доказательная база - нуль, но есть ощущение что он выдаст число максимально стремящееся к указанному снизу. Надо конечно сверху, но можно изобразить задачу от обратного - то есть находить набор элементов которые надо выложить, а не положить

Немного понял суть, но уж больно сложно это выглядит. Если совсем отчаюсь, попробую так сделать. Но по-любому должно быть какое-нибудь решение без рекурсии. За идею спасибо.

Почитал примеры, мне кажется, что это немного не то. Мне нужно число не максимально стремящееся снизу, а максимально стремящееся сверху. Попробую переделать потом этот алгоритм. Хотя фактически нужно просто поменять некоторые части местами. В общем, мощно вышло. Никогда бы до такого не додумался. Аплодирую!

Хотя я еще немного подумал и понял, что парой перестановок тут никак не обойтись. Придется посидеть, но все равно слишком много времени такая программа будет работать. Надо бы найти динамический аналог этой рекурсивной функции. Завтра еще раз попробую что-нибудь написать, может быть получится.

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

Я же говорил, это задача о рюкзаке. То есть динамическое программирование.

Изменено 10.08.2014, 18:47:05 пользователем Diplomate

[Жора 3,714]

Я вот так по диагонали пробежался - ближайшее что нашел имеет сложность N2. Так что твой N2 алгоритм с перебором не так уж плох.

А ты уверен что алгоритм имеет решение сложностью меньше чем N2?

upd: ошибся, у тебя не N2

Вообще сложность алгоритма не полиномиальная. Тут есть подзадача выбрать из N чисел несколько в сумме дающих не менее того, что надо до края "рюкзака", но с минимальной переплатой. Собственно выборка нескольких чисел из множества это уже N факториал будет в формуле ("це из н по к" надеюсь все помнят что такое в комбинаторике), а потом ещё и оптимизация - минимум из сумм.

Ну вот погуглил, так и есть. Это одна из NP-полных задач. Короче, при большом N, возможно даже меньшем чем можно подумать, комп просто не сможет её решить и повиснет.

Изменено 10.08.2014, 19:16:34 пользователем Жора

[Diplomate 3,114]

Составил программку, выполняющую подзадачу, описанную в первом посте темы. Проверил ее на нескольких тестах, вроде работает. Осталось только всунуть ее в саму задачу и наблюдать за результатом.

Так, интеграция произведена. Вроде все ОК. Осталось только дописать вывод и можно сдавать задачу.

Изменено 11.08.2014, 14:45:57 пользователем Diplomate

[mr_john 1,486]

Составил программку, выполняющую подзадачу, описанную в первом посте темы. Проверил ее на нескольких тестах, вроде работает. Осталось только всунуть ее в саму задачу и наблюдать за результатом.

Так, интеграция произведена. Вроде все ОК. Осталось только дописать вывод и можно сдавать задачу.

Кинь код, тоже интересно

[Diplomate 3,114]

Кинь код, тоже интересно

Ну что ж, программа прошла половину тестов. Походу где-то есть ошибочка. А тебе кинуть код чего: всей программы или только подпрограммы? И это будет немного затруднительно, так как я пишу на Free Pascal.

[mr_john 1,486]

Ну что ж, программа прошла половину тестов. Походу где-то есть ошибочка. А тебе кинуть код чего: всей программы или только подпрограммы? И это будет немного затруднительно, так как я пишу на Free Pascal.

Подзадачи код.

И это будет немного затруднительно, так как я пишу на Free Pascal.

Так тебе его все равно набирать на самом сайте придется, нет разве?

[Diplomate 3,114]

Подзадачи код.

Так тебе его все равно набирать на самом сайте придется, нет разве?

Нет, не придется. На сайт нужно загружать файл. Программа не очень маленькая, печатать ее будет долго. Может скинуть тебе файл? У тебя есть какой-нибудь Паскаль? На Делфи может тоже пойдет.

[mr_john 1,486]

Нет, не придется. На сайт нужно загружать файл. Программа не очень маленькая, печатать ее будет долго. Может скинуть тебе файл? У тебя есть какой-нибудь Паскаль? На Делфи может тоже пойдет.

Кидай файл, fpc имеется

[Diplomate 3,114]

Кидай файл, fpc имеется

Вот архив с программой.

pack2.rar