Во-первых, давайте считать в копейках. Умножте все цены на 100 перед началом алгоритма, и поделите на 100 при выводе. Потому что никогда нельзя деньги считать или хранить в вещественных числах. При сериализации и внешних интерфейсах, конечно, придется запятые ставить, но лучше при выводе выводить
x/100, "," и
x%100. И молиться, что у читателя хватит точности это прочитать, если он, конечно, не заморачивается с подобным трюком.
Далее алгоритм (на псевдокоде):
total_price - изначальная цена. goods[i].price - цена товара, goods[i].amount - количество товара, discount - сколько скидки.
discount_left = discount
for i in 1..n {
cur_discount = discount * goods[i].price / total_price # целочисленное деление нацело с округлением вниз.
goods[i].price -= cur_discount
discount_left -= cur_discount*goods[i].amount
}
for i in 1..n {
if discount_left == 0: break
if goods[i].amount <= discount_left {
goods[i].price -= 1;
discount_left -= goods[i].amount
} else {
// разбиваем категорию на 2 штуки, в одной discount_left товаров, в другой остальное.
new_good = Good{.price = goods[i].price-1, .amount = discount_left}
goods[i].amount -= discount_left
discount_left = 0
goods.append(new_good)
break
}
}
Как это работает: если бы мы могли идеально делить копейки с любой точностью, то каждый товар получил бы скидку price*discount/total_price. Одинаковый процент скидки везде. но у нас-то целые копейки, поэтому если мы эти скидки округлим вниз, то мы сколько-то копеек недоскинем. Но для каждой штуки товара мы потеряли меньше одной копейки, а значит суммарно - меньше общего количества товаров. Значит можно из каких-то товаров вычесть 1 и все сойдется. Вот и вычитаем из первых discount_left товаров. Если категория целиком покрыта - просто уменьшаем у нее цену. Если нет, то разбиваем на 2 куска и у одного цену уменьшаем.
Тут могут быть проблемы, если скидка очень большая и есть товары очень маленькой стоимости. Скажем, товар стоимостью 5 копеек и кидка в 85% уже между 0 и 1. Округленная вниз она будет 4, но вот если вы из этого товара потом еще и 1 вычтите, то может так получится, что вы снизите цену до 0. Допустимо ли это? Чтобы этого избежать надо товары отсортировать по убыванию цены. Но все равно может не помочь, тогда надо тогда такие товары ценой в 1 копейку исключить из рассмотрения и запустить цикл вычитания 1 опять, если после цикла discount_left не 0.
Второй момент, если вам очень хочется избегать разбиения категорий на части, то можно попробовать реализовать динамическое программирование для решения
задачи размена монет, и таким образом найти какие категории надо взять целиком, чтобы набрать discount_left. Но вряд ли вам это так уж надо, ибо предвижу весьма частый случай, когда разбивать все-равно придется. Да и разбиение тут максимум одно происходит.
