アルゴリズムコースの古いメモをいくつか確認していますが、動的計画法の問題は少し注意が必要です。いくつかの金種x1、x2、... xnのコインが無制限に供給され、ある値Xを変更したいという問題があります。動的プログラムを設計して、Xの変更が可能かどうかを判断しようとしています。作られるかどうか（コインの数を最小化しない、またはどのコインを返すか、正誤問題）。
私はこの問題についていくつか考えました、そしてそれが次のようなものであるところでこれを行う再帰的な方法を見ることができます...
MakeChange(X, x[1..n this is the coins])
for (int i = 1; i < n; i++)
{
if ( (X - x[i] ==0) || MakeChange(X - x[i]) )
return true;
}
return false;
これを動的プログラムに変換することは、私にはそれほど簡単ではありません。どうすればこれにアプローチできますか？
あなたのコードは良いスタートです。再帰的なソリューションを動的プログラミングのソリューションに変換する通常の方法は、「トップダウン」ではなく「ボトムアップ」で行うことです。つまり、再帰的な解決策が特定の X に対して小さい x の値を使用して何かを計算する場合、代わりに小さい xから同じことを計算し、それをテーブルに入れます。
あなたの場合、MakeChange 再帰関数を canMakeChange テーブルに変更します。
canMakeChange[0] = True
for X = 1 to (your max value):
canMakeChange[X] = False
for i=1 to n:
if X>=x[i] and canMakeChange[X-x[i]]==True:
canMakeChange[X]=True
以下の私のソリューションは、すべてのソリューションを計算し、最新の最適なソリューションをキャッシュする貪欲なアプローチです。現在実行中のソリューションが既にキャッシュされたソリューションよりも大きい場合は、パスを中止します。最高のパフォーマンスを得るには、金額が降順である必要があることに注意してください。
import java.util.ArrayList;
import java.util.List;
public class CoinDenomination {
int denomination[] = new int[]{50,33,21,2,1};
int minCoins=Integer.MAX_VALUE;
String path;
class Node{
public int coinValue;
public int amtRemaining;
public int solutionLength;
public String path="";
public List<Node> next;
public String toString() { return "C: "+coinValue+" A: "+amtRemaining+" S:"+solutionLength;}
}
public List<Node> build(Node node)
{
if(node.amtRemaining==0)
{
if (minCoins>node.solutionLength) {
minCoins=node.solutionLength;
path=node.path;
}
return null;
}
if (node.solutionLength==minCoins) return null;
List<Node> nodes = new ArrayList<Node>();
for(int deno:denomination)
{
if(node.amtRemaining>=deno)
{
Node nextNode = new Node();
nextNode.amtRemaining=node.amtRemaining-deno;
nextNode.coinValue=deno;
nextNode.solutionLength=node.solutionLength+1;
nextNode.path=node.path+"->"+deno;
System.out.println(node);
nextNode.next = build(nextNode);
nodes.add(node);
}
}
return nodes;
}
public void start(int value)
{
Node root = new Node();
root.amtRemaining=value;
root.solutionLength=0;
root.path="start";
root.next=build(root);
System.out.println("Smallest solution of coins count: "+minCoins+" \nCoins: "+path);
}
public static void main(String args[])
{
CoinDenomination coin = new CoinDenomination();
coin.start(35);
}
}
再帰的ソリューションにメモ化ステップを追加するだけで、動的アルゴリズムはすぐに外れます。次の例はPythonです。
cache = {}
def makeChange(amount, coins):
if (amount,coins) in cache:
return cache[amount, coins]
if amount == 0:
ret = True
elif not coins:
ret = False
elif amount < 0:
ret = False
else:
ret = makeChange(amount-coins[0], coins) or makeChange(amount, coins[1:])
cache[amount, coins] = ret
return ret
もちろん、デコレータを使用して自動メモ化することで、より自然なコードを作成できます。
def memoize(f):
cache = {}
def ret(*args):
if args not in cache:
cache[args] = f(*args)
return cache[args]
return ret
@memoize
def makeChange(amount, coins):
if amount == 0:
return True
elif not coins:
return False
elif amount < 0:
return False
return makeChange(amount-coins[0], coins) or makeChange(amount, coins[1:])
注：投稿した非動的プログラミングバージョンでさえ、あらゆる種類のエッジケースのバグがありました。そのため、上記のmakeChangeはあなたのバージョンよりもわずかに長くなっています。
コインの値が任意である一般的なケースでは、あなたが提示している問題はナップザック問題と呼ばれ、NP 完全 ( Pearson, D. 2004 )に属することが知られているため、次のような多項式時間では解けません。動的プログラミング。
x[2] = 51、x[1] = 50、x[0] = 1、X = 100 の病理学的例を取り上げます。その場合、アルゴリズムは、コイン x[2 ]、代わりに x[1] で始まる変更を行います。貪欲なアルゴリズムとしても知られている国家硬貨で使用される最初のステップは、「稼働中の合計よりも少ない最大の硬貨を使用する」ということですが、病的な硬貨では機能しません。代わりに、そのようなアルゴリズムは、それらを NP 完全に認定する組み合わせ爆発を経験します。
実際に実際に使用されているすべてのものなど、特定の特別なコイン値の取り決めには、架空のシステム X[i+1] == 2 * X[i] を含め、非常に高速なアルゴリズムがあり、架空のシステムでは O(1) でさえあります。最良の出力を決定するために、与えられたケース。これらのアルゴリズムは、コインの値のプロパティを利用します。
私は、動的プログラミング ソリューションを認識していません。つまり、プログラミングのモチーフで必要とされる最適なサブソリューションを利用するソリューションです。一般に、動的計画法で問題を解決できるのは、サブ問題に分解でき、最適に解決されたときに、証明可能な最適解に再構成できる場合のみです。つまり、問題の最適なサブソリューションを再構成すると最適なソリューションが得られることをプログラマーが数学的に実証 (「証明」) できない場合、動的計画法は適用できません。
動的計画法の一般的な例として、複数の行列の乗算への適用があります。行列のサイズに応じて、A · B · Cを 2 つの同等の形式 (( A · B ) · C ) または ( A ·( B · C )) のいずれかとして評価する選択は、さまざまな計算につながります。掛け算と足し算の量。つまり、一方の方法が他方の方法よりも最適 (高速) です。動的計画法は、さまざまな方法の計算コストを表にして、動的に計算されたスケジュール (またはプログラム)に従って実際の計算を実行するモチーフです。実行時に。
重要な機能は、すべての可能な組み合わせの列挙ではなく、計算されたスケジュールに従って計算が実行されることです。列挙が再帰的に実行されるか反復的に実行されるかに関係なく。行列の乗算の例では、各ステップで最小コストの乗算のみが選択されます。その結果、中間コストの準最適スケジュールの可能なコストは計算されません。つまり、考えられるすべてのスケジュールから最適なスケジュールを探すのではなく、ゼロから最適なスケジュールを段階的に構築してスケジュールを計算します。
「動的計画法」という命名法は、「スケジュールする」という意味でも「プログラム」が使用される「線形計画法」と比較することができます。
動的計画法の詳細については、Cormen、Leiserson、Rivest、および Stein による「Introduction to Algorithms」という、私が知っているアルゴリズムに関する最高の本を参照してください。 「Rivest」は「RSA」の「R」であり、動的計画法はスコアの 1 つの章にすぎません。
この論文は非常に関連性があります: http://ecommons.library.cornell.edu/handle/1813/6219
基本的に、他の人が言ったように、任意のXを任意の金種セットで合計する最適な変更を行うことはNP困難です。つまり、動的計画法はタイムリーなアルゴリズムを生成しません。この論文では、貪欲なアルゴリズムが特定の金種のセットに対して常に最適な結果を生成するかどうかを判断するための多項式時間 (つまり、入力のサイズの多項式であり、以前のアルゴリズムを改善したもの) アルゴリズムを提案します。
これは、特定の合計に必要なコインの最小数を見つけるための参照用の c# バージョンです。
(詳細については、私のブログ @ http://codingworkout.blogspot.com/2014/08/coin-change-subset-sum-problem-with.htmlを参照してください)
public int DP_CoinChange_GetMinimalDemoninations(int[] coins, int sum)
{
coins.ThrowIfNull("coins");
coins.Throw("coins", c => c.Length == 0 || c.Any(ci => ci <= 0));
sum.Throw("sum", s => s <= 0);
int[][] DP_Cache = new int[coins.Length + 1][];
for (int i = 0; i <= coins.Length; i++)
{
DP_Cache[i] = new int[sum + 1];
}
for(int i = 1;i<=coins.Length;i++)
{
for(int s=0;s<=sum;s++)
{
if (coins[i - 1] == s)
{
//k, we can get to sum using just the current coin
//so, assign to 1, no need to process further
DP_Cache[i][s] = 1;
}
else
{
//initialize the value withouth the current value
int minNoOfCounsWithoutUsingCurrentCoin_I = DP_Cache[i - 1][s];
DP_Cache[i][s] = minNoOfCounsWithoutUsingCurrentCoin_I;
if ((s > coins[i - 1]) //current coin can particiapte
&& (DP_Cache[i][s - coins[i - 1]] != 0))
{
int noOfCoinsUsedIncludingCurrentCoin_I =
DP_Cache[i][s - coins[i - 1]] + 1;
if (minNoOfCounsWithoutUsingCurrentCoin_I == 0)
{
//so far we couldnt identify coins that sums to 's'
DP_Cache[i][s] = noOfCoinsUsedIncludingCurrentCoin_I;
}
else
{
int min = this.Min(noOfCoinsUsedIncludingCurrentCoin_I,
minNoOfCounsWithoutUsingCurrentCoin_I);
DP_Cache[i][s] = min;
}
}
}
}
}
return DP_Cache[coins.Length][sum];
}
i再帰的に書き込む場合は、メモリベースの検索を使用するだけで問題ありません。計算したものを保存する必要がありますが、これは再度計算されることはありません
int memory[#(coins)]; //initialize it to be -1, which means hasn't been calculated
MakeChange(X, x[1..n this is the coins], i){
if(memory[i]!=-1) return memory[i];
for (int i = 1; i < n; i++)
{
if ( (X - x[i] ==0) || MakeChange(X - x[i], i) ){
memory[i]=true;
return true;
}
}
return false;
}