Алгоритм: Покупка коллекции товаров с ваучерами

Question

Я изо всех сил, чтобы придумать решение для этой задачи для алгоритмов курса:

Вы идете в магазин и хотите купить п = {п , n , ..., n _n} товар, где предметы могут быть разными или нет.

В магазине проводится следующее продвижение по службе: «Если клиент покупает две статьи, чьи цены складываются до значения, которое заканчивается на 11, 33 или 55 центов, он получит ваучер, соответствующий соответствующему значению цен».

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

Например: Если вам нужно купить 3 продукты (п , п , п) с ценами (1.01 $, 2.10 $ и 3 $), вы должны купить п и n вместе и купите n отдельно, с общей стоимостью: (1.01 + 2.10) + 3 - (0.11) = 6 $.

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

Answer 1

Сортировка товаров, которые вы хотите купить по ценным ценам ... т. Е. (25.01 $, 1.02 $, ..., 0.99 $).

И тогда проверьте ... ли какой-либо из центах сумма до 0.99 $ ... Это легко решить по двум суммам ... Вы берете 0,01 $ и ищите его комплимент 0,98 $ с помощью двоичного кода search ... Удалите эту пару и повторите, пока не найдете пары продуктов с центами, которые суммируются до 0.99 $.

Если это сделано, удалите найденные пары продуктов ... подсчитайте свою прибыль и проверьте, составляет ли какой-либо из центов до 0,88 $ ... Точно так же.

...

Если это будет сделано, удалить найденные пары продуктов ... и проверить любое ли из центов суммы до 0.11 $ ... таким же образом.

Это все O(nlogn) сложность;)