0

私はコインのソートされた辞書を持っています - 各キーはコインであり、値はその特定の金種で利用可能なコインの数です。ここで、金額を指定して、正確な金額に一致するすべてのコイン (またはその金額に加算されるコイン、好みはパフォーマンス) を辞書から取り出したいと考えています。

いくつかのシナリオ例を次に示します。

  • リポジトリに 3 つのコイン (1p コイン 2 つと 5p コイン 1 つ) があり、要求が 2p の場合、1p コイン 2 つを返し、リポジトリには 5p コインが 1 つしかありません。

  • リポジトリに 6 つのコインがあり、5 つの 1p コインと 1 つの 5p コインがあり、リクエストが 5p の場合、最初の 5 つの 1p コインまたは 1 つの 5p コインのどちらかを返すことができます。最小限のルックアップ。

  • リポジトリに 2 つのコインがあり、2 つの 1p コインがあり、要求が 1 つの 5p に対するものである場合、残高が不足しているという例外がスローされます。

  • リポジトリに 1 つのコインと 1 つの 5p コインがあり、リクエストが 1p の場合、変更が利用できないという例外をスローします (例外がこれらを通信するための正しい方法であるかどうかはわかりません)。

クラスは次のとおりです。

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

コインに Worth という名前のプロパティがあり、辞書がコインの価値によって降順で並べられていると仮定すると、次のように実行できます。

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 に答える