特定の合計の銀行券の組み合わせを見つける

Question

効率的にお金を出す方法。たとえば、100 $の銀行紙幣1枚、50 $の銀行券1枚、30 $の2枚の紙幣があります。 110 $要約を達成するために50 $と30 $の2つが必要であると判断する方法。

換言すれば、30ドル（銀行券2枚）、50ドル（銀行券1枚）、100ドル（銀行券1枚）の固定番号があります。問題は、特定の合計を得るために取るべき銀行券を決定することです（例えば、110 $）。この場合、30ドル紙幣2枚と50ドル紙幣1枚を払う必要があります。

ここでグリーディアルゴリズムを使用することはできません。最初に100 $銀行券を取ると、110 $要約を達成できないためです。

紙幣を保管するために使用するデータ構造はどれですか？単純に各銀行券タイプの数量、または各銀行券を保管する配列でもよい。[100,50,30,30]

そして、特定の合計を得るために必要な銀行券を見つけるアルゴリズムとは何ですか？

Answer 1

動的プログラミング手法を使用できます。配列には、インデックスが到達可能な合計と、この合計に達する値 - 請求番号が格納されます。

このアプローチは、Emercoinトランザクションオプティマイザで使用されます。で 参照ソースコード：

https://github.com/Emercoin/emercoin/blob/master/src/wallet.cpp#L1112

メモリはO（合計）です。時間はOです（合計* NumBills）。 それについて短い記事を参照してください。

http://cointelegraph.com/news/emercoin-implements-solution-to-reduce-blocksize-inflation

Answer 2

がCoin Change Problem

また、問題のような種類のために、この質問に私の解決策を参照してください、ハードの部分は、コイン/マネーシステムが正規のかどうかを判断することは常にあるすなわち欲張りアルゴリズムを使用することができます