Алгоритм (Pascal)

[Besidnuk]

Есть такая задача:

Покупатель имеет купюры номиналом А1, А2 ...,Аn, а продавец - В1, В2 ...,Вn. Необходимо найти максимальную стоимость товара Р, какой покупатель не сможет купить из-за того, что не имеет возможности точно рассчитаться за этот товар с продавцом, хотя денег на покупку этого товара у него достаточно.

Входные данные:
строка 1: натуральное число N - количество разных номиналов купюр (1<=N<=10); следующие N строк: тройка натуральных чисел - номиналом купюры (Ск), количество купюр данного номиналу у покупателя (Хк), количество купюр данного номиналу у продавца (Yк).

Выходные данные: Одно натуральное число Р - максимальная стоимость товара, какой покупатель не сможет купить, или 0, если покупатель сможет рассчитаться за любой товар в пределах наличия у него суммы.

Пример:

Входные:

7
1 0 3
2 0 0
5 0 1
10 0 2
20 0 0
50 1 0
100 2 0

Выходные

246

Я думаю тут нужно сначала посчитать сколько будет денег у покупателя. Ето можна зделать за формулой: max = С1*Х1+С2*Х2+...+Сn*Xn. Потом записать в масив все здачи которые может дать продавец. Ну и там отнимать у мах по одному и смотреть может ли дать здачу продавец. А вот и вопрос: За каким алгоритмом можна записать все здачи? Сколько думал, никак не могу придумать.

[Besidnuk]

никто не знает подходящего алгоритма?

[Z1000000]

Удалил! Написал ошибочное решение.

[Serge_Bliznykov]

Besidnuk
задача сводится к тому, чтобы по заданному массиву с купюрами для любого N получить, можно ли это N выдать через имеющиеся купюры.

честно говоря, я вижу решение только через использование рекурсивной функции (для убыстрения можно использовать отсечение вариантов используя рекурсию c отходом назад), через которую перебирать все варианты. Как только нашли подходящий вариант - выход.

считаем SumMax (максимальную сумму у покупателя).
ну и дальше, уже так, как Вы сказали. крутим цикл от 1 до SumMax - проверяя, может ли это число быть выдано имеющимися у продавца купюрами (кстати, при этом надо брать все купюры и которые у него есть, и у покупателя)...
Как только нашли число, которое НЕ МОЖЕТ быть выдано,
сразу ответ SumMAX - НайденноеЧисло..
если дошли до SumMAX не нашли - значит ответ 0


p.s. если Вам реально нужно и других вариантов решения не нашли и самостоятельно такую функцию написать не получается - пишите, попробую набросать...

[Besidnuk]

Сообщение от Serge_Bliznykov

Besidnuk
задача сводится к тому, чтобы по заданному массиву с купюрами для любого N получить, можно ли это N выдать через имеющиеся купюры.

честно говоря, я вижу решение только через использование рекурсивной функции (для убыстрения можно использовать отсечение вариантов используя рекурсию c отходом назад), через которую перебирать все варианты. Как только нашли подходящий вариант - выход.

считаем SumMax (максимальную сумму у покупателя).
ну и дальше, уже так, как Вы сказали. крутим цикл от 1 до SumMax - проверяя, может ли это число быть выдано имеющимися у продавца купюрами (кстати, при этом надо брать все купюры и которые у него есть, и у покупателя)...
Как только нашли число, которое НЕ МОЖЕТ быть выдано,
сразу ответ SumMAX - НайденноеЧисло..
если дошли до SumMAX не нашли - значит ответ 0


p.s. если Вам реально нужно и других вариантов решения не нашли и самостоятельно такую функцию написать не получается - пишите, попробую набросать...

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

[Serge_Bliznykov]

тему пока не будем закрывать, у нас тут на форуме есть "олимпийцы", попрошу их заглянуть сюда, они что-инбудь ещё обязательно придумают...
вот, хорошо бы LeBron сюда зашёл.. Он реально Гуру!

Ну а рекурсией я пользоваться еще не умею.

Вместо рекурсии можно и перебор прицепить. Просто рекурсией, мне кажется, проще выглядит решение...

Кстати, весьма напрасно не умеете... инструмент, конечно, довольно специфический (далеко не для всех задач имеет смысл его применять), но зато, если он уж подходит - то чрезвычайно мощная штука... для ознакомления, почитайте, например, тут - Методы программрования: переборные алгоритмы

[Besidnuk]

Сообщение от Serge_Bliznykov

тему пока не будем закрывать, у нас тут на форуме есть "олимпийцы", попрошу их заглянуть сюда, они что-инбудь ещё обязательно придумают...
вот, хорошо бы LeBron сюда зашёл.. Он реально Гуру!



Вместо рекурсии можно и перебор прицепить. Просто рекурсией, мне кажется, проще выглядит решение...

Кстати, весьма напрасно не умеете... инструмент, конечно, довольно специфический (далеко не для всех задач имеет смысл его применять), но зато, если он уж подходит - то чрезвычайно мощная штука... для ознакомления, почитайте, например, тут - Методы программрования: переборные алгоритмы

Спасибо, почитаю)