0

我有一个排序的硬币字典 - 每个键都是一个硬币，值是该特定面额的可用硬币数量。现在，给定一个数量，我想从字典中取出所有与确切数量匹配的硬币（或加起来等于该数量的硬币，偏好是性能）。

以下是一些示例场景：

  • 如果我在仓库中有 3 个硬币，有两个 1p 硬币和一个 5p 硬币，如果请求是 2p，那么我还给两个 1p 硬币，我的仓库只有一个 5p 硬币。

  • 如果我在存储库中有 6 个硬币，其中有 5 个 1p 硬币和 1 个 5p 硬币，如果请求是 5p，那么我可以退回前 5 个 1p 硬币或只退回 1 个 5p 硬币，这在以下方面表现更好最少的查找。

  • 如果我在存储库中有 2 个硬币，有两个 1p 硬币，如果请求是一个 5p，那么我会抛出一个异常，说余额不足。

  • 如果我在存储库中有一枚硬币，有一枚 5 便士硬币，并且请求是 1 便士，那么我会抛出一个异常，说零钱不可用。（不确定异常是否是传达这些的正确方式）。

这是课程：

public class CoinRepository :ICoinRepository
{
    private readonly SortedDictionary<Coin, int> repository;

    public CoinRepository()
    {
        repository = new SortedDictionary<Coin, int>();
    }

    public void Add(List<Coin> coins)
    {
        foreach (var coin in coins)
        {
            repository[coin] = repository.ContainsKey(coin) ? repository[coin] + 1 : 1;               
        }
    }

    public Dictionary<Coin, int> GetCoins(int balance)
    {
        if (repository.Count == 0)
            throw new NoBalanceAvailiable();

        //How?
        return new Dictionary<Coin, int>();
    }
}


 public class Coin
   {
     public int CoinValue { get; set; }
    //Has equals, hascode etc implemented. Omitted here for brevity.
   }

我希望有一些 LINQ 扩展可以解决这个问题，你能帮忙吗？

注意：可以更改任何或所有数据结构，唯一的目标是找到平衡。

谢谢，-迈克

4

1 回答 1

1

假设 coin 有一个名为 Worth 的属性，并且字典按 coin value 降序排列，可以这样做：

public Dictionary<Coin, int> GetCoins(int balance)
{
    var result = new Dictionary<Coin, int>();

    foreach (var pair in repository) {
        while (balance - pair .Key.Worth>0 && pair.Value>0 )
        {
            balance -= pair.Key.Worth;  
            pair.Value--;              
            if (!result.ContainKey(coin.key)) result[pair.key] = 0;
            result[coin.key]++;
        } 
        if (balance == 0) break;
    }

    if (balance == 0) { 
        // pair is a struct, so repository does not change when pair.Value is modified,
        // so if we find a solution, repository has to be updated
        foreach (var pair in result) repository[pair.key] -= pair.Value;
        return result;
    }

    return null;
}
于 2013-09-20T09:22:27.093 回答