C# + LINQ Как выдать сдачу монетами?

Question

Есть таблица с полями Denomination (номинал) и Quantity (количество). В таблице 4 номинала 1, 2, 5, 10 и, соответственно, 4 строки.

Есть сумма сдачи: public int changeTotal = 159;

Эту сумму надо выдать любыми монетами, которые есть в наличии. В коде это значит заполнить этот словарь: public Dictionary<int, int> Change { get; init; } = new () { { 1, 0 }, {2, 0}, {3, 0}, {4, 0} };

Вот вынули все монеты: var allCoins = await _dbContext.Coins.ToListAsync();

Что дальше делать?

Answer 1

При ограниченном количестве монет каждого номинала заполняем массив int A[] размером changeTotal+1 нулями, в нулевую ячейку пишем -1. Затем для каждого номинала Denomination[i] проходим Quantity[i] раз конца массива к началу. Если A[k-Denomination[i]] не равно нулю, то мы можем составить сумму k с использованием монеты Denomination[i] и набора из указанной ячейки. Для запоминания набора можно в k-ю ячейку записать текущий номинал.

По окончанию работы, если A[changeTotal] не равно нулю, то сумму набрать можно, и мы можем восстановить набор, пропрыгав по ячейкам справа налево

При наличии неограниченного количества монет можно использовать жадный алгоритм (данный набор номиналов это позволяет) - разделить оставшуюся сумму на самый большой номинал 159 / 20, получить семь двугривенных, повторить с остатком (19) и следующим номиналом, и так далее, пока остаток не станет нулевым

Answer 2

Это слой 'репозиторий'. Хотя такое должно лежать в сервисах, как бизнес-логика.

public async Task<Dictionary<int, int>> Update(int total,
                                                      Dictionary<int, int> inserted, 
                                                      Dictionary<int, int> change)
        {
            // что лежит в БД сейчас, вернёт другой метод
            Dictionary<int, int> available = await GetAllCoinsLikeDict(); 
            int insertedTotal = 0;

            // внесение оплаты
            foreach (var c in inserted)
            {
                await _dbContext.Coins
                    .Where(coin => coin.Denomination == c.Key)
                    .ExecuteUpdateAsync(coin => coin
                    .SetProperty(o => o.Quantity, o => o.Quantity + c.Value));
                
                insertedTotal += c.Key * c.Value;
            }

            // сдача числом
            double totalDiff = insertedTotal - total;
            // промежуточная сумма сдачи
            double rest = totalDiff;

            // сдача словарём
            if (rest <= 0)
            {
                return change;
            }
            else
            {
                foreach (var d in change.Keys.Reverse())
                {
                    double need = Math.Floor(rest / d);
                    double value = available[d];
                    double take = (int)Math.Min(need, value);
                    change[d] = (int)take;
                    available[d] -= (int)take;
                    await _dbContext.Coins
                        .Where(coin => coin.Denomination == d)
                        .ExecuteUpdateAsync(coin => coin
                        .SetProperty(o => o.Quantity, o => o.Quantity - (int)take));
                    rest -= take * d;
                }
            }

            return change;            
        }

БЛОГ НА HUSL

C# + LINQ Как выдать сдачу монетами?

Ответы (2 шт):