0

この問題では、特定のコストでコインの交換回数を数える必要があります。

たとえば、コインの価値がである場合50, 20, 10, 5, 1、次のコストを形成できます。

5 =>（5）、（11111）、これは2つの方法です。

10 =>（10）、（5、5）、（5、11111）、（11111、11111）、これらは4つの方法です。

これが私の機能です。10のコストから物乞いする間違った結果を返しています（実際のウェイ数はわずか4であるのに対し、9ウェイを返します）

int dp[10000];
int coins[] = { 50, 20, 10, 5, 1 };
int rec(int n)
{
  if (n == 0) return 1;
  if (dp[n] != -1) return dp[n];
  int cnt = 0;
  for (int i = 0; i < 5; i++)
    if (coins[i] <= n) cnt += rec(n - coins[i]);
  return dp[n] = cnt;
}

この関数を修正して、正しい数の方法を提供するにはどうすればよいですか？このアルゴリズムは正しいですか？ここで完全なコードとその出力を参照してください

注：私の問題はdp配列の初期化ではありません。を呼び出す前に毎回memset初期化するために使用しています。-1rec

4

3 に答える 3

3

(5, 1, 1, 1, 1, 1) と (1, 1, 1, 5, 1, 1) は、アルゴリズムでは異なる方法です。減少させ続ける必要があります。

int dp[10000][5];  // dp[20][2] means, if the biggest coin is coins[2],
                   // how much ways for 20 ?
int coins[] = { 1, 5, 10, 20, 50 }; // here
int rec(int n, int m)
{
  int cnt = 0;
  int i;
  if (n == 0) return 1;
  //if (m == 0) return 1;
  if (dp[n][m] != -1) return dp[n][m];
  for (i = 0; i <= m; i++)
    if (coins[i] <= n) cnt += rec(n - coins[i], i);
  return dp[n][m] = cnt;
}

int main()
{
        memset(dp, -1, sizeof(dp));
        printf("%d\n", rec(10, 4));
}
于 2012-08-08T09:17:42.060 に答える
1

アルゴリズムが 5 コインで始まることを確認していないため、結果は間違っています。(5,11111) はコード内で (1, 5, 1111) と同じように有効ですが、これは同じ結果です。あなたの結果は、10 以上ではなく、6 以上から間違っているはずです。

これを修正するには、関数 rec() でカットオフのようにすることができます。

int rec(int n, int cutoff)
{
  if (n == 0) return 1;
  if (dp[n] != -1) return dp[n];
  int cnt = 0;
  for (int i = cutoff; i < 5; i++)
    if (coins[i] <= n) cnt += rec(n - coins[i], i);
  return dp[n] = cnt;
}

やるべきです。

編集: dp[] 配列はこのカットオフを気にしないため、注意する必要がありますが、これは一般に、実行している障害です。その行にコメントを付けて、これが機能するかどうかを確認できます。

于 2012-08-08T09:08:46.923 に答える
1

1 つの備考: 初期化

memset(dp, -1, sizeof dp);

本当に安全ではありません。メモリ空間のmemsetすべてのバイトを初期化します ( http://www.cplusplus.com/reference/clibrary/cstring/memset/を参照)。この特定のケースでは、あなたは幸運で、 の表現int(-1)は (おそらく) 4 回と同じですunsigned char(-1)。

std::fill（http://www.cplusplus.com/reference/algorithm/fill/ ）を使用することをお勧めします。

于 2012-08-08T09:12:18.487 に答える