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

[Diplomate 3,115]

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

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. На киберфоруме задавал этот вопрос, но никто не ответил. Может хоть тут кто-нибудь подскажет мне, как это сделать? В награду могу перечислить виры и проставить спасибки.

[Rogvald 1,522]

Да поможет тебе Аллах.(с)

[Diplomate 3,115]

Да поможет тебе Аллах.(с)

Молился и не раз.

[mr_john 1,486]

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

Но это так, на скорую руку. Счас еще посижу, может че еще предложу.

Еще один вариант, проверять массив на максимум и два-три минимума, а потом проверить: какая сумма меньше. В 90% случаев она минимальна. Протестил простенькой программой

[Diplomate 3,115]

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

Но это так, на скорую руку. Счас еще посижу, может че еще предложу.

Жадный алгоритм тут совсем ни к чему. Это одна из задач о так называемых рюкзаках. В обычном варианте она выглядит так: Есть n предметов, обладающих массой и стоимостью. Нужно набить ими рюкзак вместимостью m, чтобы он был максимально дорогим. Я же разбил задачу Пицца на ряд подзадач, в одной из которых мне нужно сделать то, что я написал в шапке.

Возможно, это вообще не требуется, тогда буду благодарен, если вы предоставите мне другой рабочий алгоритм.

[mr_john 1,486]

Жадный алгоритм тут совсем ни к чему. Это одна из задач о так называемых рюкзаках. В обычном варианте она выглядит так: Есть n предметов, обладающих массой и стоимостью. Нужно набить ими рюкзак вместимостью m, чтобы он был максимально дорогим. Я же разбил задачу Пицца на ряд подзадач, в одной из которых мне нужно сделать то, что я написал в шапке.

Возможно, это вообще не требуется, тогда буду благодарен, если вы предоставите мне другой рабочий алгоритм.

Дык что конкретно решать надо?

Если это:

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

То вот примерный алгоритм:

Еще один вариант, проверять массив на максимум и два-три минимума, а потом проверить: какая сумма меньше. В 90% случаев она минимальна. Протестил простенькой программой, можно сказать в любом случае такая фигня прокатит.

[Diplomate 3,115]

То вот примерный алгоритм:

Ты наверняка вводил "человеческие" тесты, а на сайте informatics и на олимпиадах такое вряд ли прокатит. У меня пока только одна догадка: если вес рюкзака должен быть более m, то можно сначала проверить, можно ли набрать рюкзак массой m+1, потом m+2 и так делать до тех пор, пока не найдем набираемый рюкзак. Такой алгоритм будет работать в 100% случаев, но он жутко прожорливый и нерациональный. Даже пробовать не хочется.

[mr_john 1,486]

Ты наверняка вводил "человеческие" тесты, а на сайте informatics и на олимпиадах такое вряд ли прокатит. У меня пока только одна догадка: если вес рюкзака должен быть более m, то можно сначала проверить, можно ли набрать рюкзак массой m+1, потом m+2 и так делать до тех пор, пока не найдем набираемый рюкзак. Такой алгоритм будет работать в 100% случаев, но он жутко прожорливый и нерациональный. Даже пробовать не хочется.

Ну, тесты обычно стандартны и любому первокурснику известны.))) Я и говорю, на 100% программа вряд ли пройдет, но ведь как минимум можно сделать вывод в файл)))

Такой алгоритм будет работать в 100% случаев, но он жутко прожорливый и нерациональный. Даже пробовать не хочется.

Не знаю, я всегда юзаю нерациональные алгоритмы. Или просто неполный алгоритм, который будет менее подвержен случайностям. Собственно, я такой выше и предложил.

[MaslovRG 6,935]

del

[mr_john 1,486]

Где опытные кодеры?

[йцукенгшщз 2,498]

лето же, че он делает?

[mr_john 1,486]

лето же, че он делает?

Может на каникулы задали

[Diplomate 3,115]

Может на каникулы задали

Смешно. В 9 классе еще нет программирования. Сомневаюсь, что нечто подобное будет и в 11.

Ладно, завтра попробую покряхтеть над немного другим вариантом рюкзака для этой задачи, может получится.

Не знаю, я всегда юзаю нерациональные алгоритмы. Или просто неполный алгоритм, который будет менее подвержен случайностям. Собственно, я такой выше и предложил.

Ну, на олимпиаде каждый заваленный тест стоит баллов. Причем достаточно хотя бы одного неправильного ответа, чтобы количество баллов урезали в разы.

[mr_john 1,486]

Смешно. В 9 классе еще нет программирования. Сомневаюсь, что нечто подобное будет и в 11.

Ладно, завтра попробую покряхтеть над немного другим вариантом рюкзака для этой задачи, может получится.

Ну я то не знаю подробностей твоей учебы. У меня было, к примеру, только такой хренью мы не занимались. Да и я, хоть и на кодера уже два года как учусь, такую задачу впервые вижу. Но признаюсь честно, голова у меня хреново соображает.

Ну, на олимпиаде каждый заваленный тест стоит баллов. Причем достаточно хотя бы одного неправильного ответа, чтобы количество баллов урезали в разы.

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

И если тебя интересует именно набор баллов, а не решение задачи - обращайся

[Detech 2,184]

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

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

Выход единственный - гуглить.

[Diplomate 3,115]

Ну я то не знаю подробностей твоей учебы. У меня было, к примеру, только такой хренью мы не занимались. Да и я, хоть и на кодера уже два года как учусь, такую задачу впервые вижу. Но признаюсь честно, голова у меня хреново соображает.

Ну как бы такие задачи для хороших программистов считаются легкими.

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

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

Выход единственный - гуглить.

Я гуглил, причем очень долго. Ничего толкового найти не смог.

[Detech 2,184]

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

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

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

[Diplomate 3,115]

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

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

Не уверен, но мне почему-то кажется, что можно куда проще. В общем, попробую, может по времени пройдет.

[йцукенгшщз 2,498]

Смешно. В 9 классе еще нет программирования. Сомневаюсь, что нечто подобное будет и в 11.

Ладно, завтра попробую покряхтеть над немного другим вариантом рюкзака для этой задачи, может получится.

школы разные бывают

[Diplomate 3,115]

школы разные бывают

Жаль, что я не в той.