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

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

Не совсем понимаю приведенное решение:

Если покупатель отдаст все свои купюры продавцу, то понятно, что для решения исходной задачи размер минимальной сдачи, которую продавец не может вернуть, используя любые имеющиеся теперь у него купюры C[i] (его и покупателя). Для этого удобно отсортировать купюры согласно их достоинства в порядке неубывания.

Предположим, что продавец может вернуть любую сдачу от 1 до S, используя только меньшие i купюр. Для следующей (i+1)-ой купюры достоинства C[i+1] возможны 2 ситуации.

1. C[i+1]<S+2. Тогда понятно, что продавец может вернуть любую сдачу от 1 до C[i+1]+S, т.к. любая из этих сумм представима либо первыми i купюрами, либо (i+1)-ой купюрой вместе с некоторыми из первых i купюр.

2. C[i+1]>S+1. Тогда понятно, что продавец не может вернуть сдачу S+1.

Опишем процедуру вычисления S.
Если значение S не меньше суммарного количества денег покупателя, то покупатель может купить товар любой доступной ему стоимости, точно рассчитавшись за покупку. Иначе P=A[1]+...+A[N]-S.

1

Добрый день, смогли ли вы найти решение этой задачи? Мне нужно решить эту же задачу, а приведенное в интернете объяснение мне не понятно.

0

Mark_vl, я тоже не до конца понимаю алгоритм решения (видимо надо проходить пошагово и рассматривать конкретные расклады, чтобы понять логику решения).
но, с другой стороны, зачем тебе понимать алгоритм, если тебе на блюдечке с голубой каёмочки этот алгоритм уже расписали.
Бери его и вставляй в свою программу, твоя программа будет работать и решать поставленную задачу.
Профит.
Или тебе принципиально хочется разобраться в этой задаче, чтобы самому понимать решение?

0

Я решил эту задачу: http://www.cyberforum.ru/java-... 40984.html

0

Сообщение от Mark_vl Я решил эту задачу

ну, допустим, ты не решил, а нашёл готовый код.

Код полностью соответствует алгоритму, который приведён в пост #1 (ну и собственно, который гуглится с полпинка).
я тебе сразу же предложил написать код по данному алгоритму без всяких затей.

А зачем ты задавал вопрос в разделе PascalABC.NET, если тебе программа на Java нужна?


ну и собственно, согласен с комментарием:

Сообщение от wizard41 Mark_vl, чет долго искал. Решений этой задачи пруд пруди, почти для любого языка. Поэтому тебе никто и не отвечал, ибо задача вообще не специфическая.

0