1

コインの変更問題の解決策を理解しようとしていますが、いくつかの問題があります。

Algorithmistには、以下に示す動的プログラミング ソリューションの疑似コード ソリューションがあります。

n = goal number
S = [S1, S2, S3 ... Sm]

function sequence(n, m)
   //initialize base cases

   for i = 0 to n
     for j = 0 to m
       table[i][j] = table[i-S[j]][j] + table[i][j-1]

O(n^2)これは、2 次元配列を使用して同じ答えを何度も再計算することを避ける標準的なアルゴリズムです。

私の問題は 2 つあります。

  1. 基本ケースを定義し、table[][]初期値として組み込む方法
  2. テーブルからさまざまなシーケンスを抽出する方法

問題 1 に関しては、このアルゴリズムには 3 つの基本ケースがあります。

  • if n==0, return 1
  • if n < 0, return 0
  • if n >= 1 && m <= 0, return 0

それらを に組み込む方法がtable[][]わかりません。最後に、配列からソリューション セットを抽出する方法がわかりません。

4

1 に答える 1

2

少なくとも2つの異なるアプローチで動的計画法アルゴリズムを実装できます。1つはメモ化を使用したトップダウンのアプローチであり、もう1つはボトムアップの反復アプローチです。

動的計画法の初心者には、動的計画法の漸化式を理解するのに役立つトップダウンアプローチを最初に使用することを常にお勧めします。

したがって、コイン交換の問題を解決するために、漸化式が何を言っているかをすでに理解しています。

table[i][j] = table[i-S[j]][j] + table[i][j-1]

このような漸化式は良好ですが、境界条件がないため、それほど明確に定義されていません。したがって、無限ループに入ることなく漸化式を正常に終了できるようにするには、境界条件を定義する必要があります。

では、再帰ツリーを下に行こうとするとどうなるでしょうか。

を計算する必要がある場合、つまりコインを使用してタイプからtable[i][j]に変更するアプローチの数を計算する必要がある場合、処理する必要のあるいくつかのコーナーケースがあります。i0j

1）もしもj == 0？

有効なサブj == 0問題ではないサブ問題を解決しようとすると。table(i,j-1)したがって、1つの境界条件は次のとおりです。

if(j==0) {
  if(i==0) table[i][j] = 1;
  else table[i][j] = 0;
}

2）もしもi - S[j] < 0？

また、この境界のケースを処理する必要があります。このような状況では、このサブ問題を解決しようとしないかtable(i-S[j],j) = 0、これらすべてのケースで初期化する必要があります。

したがって、全体として、トップダウンのメモ化アプローチからこの動的計画法を実装する場合は、次のようなことができます。

int f(int i, int j) {
  if(calc[i][j]) return table[i][j];
  calc[i][j] = true;
  if(j==0) {
    if(i==0) return table[i][j]=1;
    else return table[i][j]=0;
  }
  if(i>=S[j])
    return table[i][j]=table[i-S[j][j]+table[i][j-1];
  else
    return table[i][j]=table[i][j-1];
}

実際には、table配列の値を使用して、このサブ問題が以前に計算されたかどうかを追跡することもできます（たとえば、値-1を初期化できる場合は、このサブ問題が計算されていないことを意味します）。

答えが明確であることを願っています。:)

于 2013-02-09T00:30:53.480 に答える