1

http://uva.onlinejudge.org/external/6/674.html我正在尝试解决这个问题。但请注意，这不是最小硬币找零问题，它要求我使用 50、25、15、10、5 和 1 美分硬币制作 N 美分的不同数量的方法。这很简单，所以我做了这个函数：

int count(int n, int m) // n is the N of the problem, m is the number of coin types and s[] is {1, 5, 10, 25, 50}
{
  if (n == 0)
  {
    return 1;
  }

  if (n < 0)
  {
    return 0;
  }

  if (m < 0 && n >= 1)
  {
    return 0;
  }

  return DP[n][m - 1] + DP[n - s[m]][m];
}

也相当简单的是添加带有记忆的动态编程：

int count(int n, int m)
{
  if (n == 0)
  {
    return 1;
  }

  if (n < 0)
  {
    return 0;
  }

  if (m < 0 && n >= 1)
  {
    return 0;
  }

  if (DP[n][m - 1] == -1 || DP[n - s[m]][m] == -1)
  {
    return count(n, m - 1) + count(n - s[m], m);
  }
  else
  {
    return DP[n][m - 1] + DP[n - s[m]][m];
  }
}

然而，这些都不够快——我需要自下而上的动态编程，但我在编码它时遇到了困难，即使在 Algorithmist 的帮助下——http: //www.algorithmist.com/index.php/Coin_Change。

void generate()
{
  for (i = 0; i < MAX; i++)
  {
    for (u = 0; u < m; u++)
    {
      if (i == 0)
      {
        DP[i][u] = 1;
      }
      else if (u == 0)
      {
        DP[i][u] = 0;
      }
      else if (s[u] > i)
      {
        DP[i][u] = DP[i][u - 1];
      }
      else
      {
        DP[i][u] = DP[i][u - 1] + DP[i - s[u]][u];
      }
    }
  }
}

由于某种原因，每个结果我都得到 0，这是我的完整代码：

#include <stdio.h>
#include <string.h>

using namespace std;

#define MAX 7490

int s[] = {1, 5, 10, 25, 50}, m = 5, input, DP[MAX][5], i, u;

int count(int n, int m)
{
  if (n == 0)
  {
    return 1;
  }

  if (n < 0)
  {
    return 0;
  }

  if (m < 0 && n >= 1)
  {
    return 0;
  }

  if (DP[n][m - 1] == -1 || DP[n - s[m]][m] == -1)
  {
    return count(n, m - 1) + count(n - s[m], m);
  }
  else
  {
    return DP[n][m - 1] + DP[n - s[m]][m];
  }
}

void generate()
{
  for (i = 0; i < MAX; i++)
  {
    for (u = 0; u < m; u++)
    {
      if (i == 0)
      {
        DP[i][u] = 1;
      }
      else if (u == 0)
      {
        DP[i][u] = 0;
      }
      else if (s[u] > i)
      {
        DP[i][u] = DP[i][u - 1];
      }
      else
      {
        DP[i][u] = DP[i][u - 1] + DP[i - s[u]][u];
      }
    }
  }
}

int main()
{
  memset(DP, -1, sizeof DP);
  generate();

  while (scanf("%d", &input) != EOF)
  {
    //printf("%d\n", count(input, 4));
    printf("%d\n", DP[input][4]);
  }

  return 0;
}
4

1 回答 1

3

你在这里犯了错误：

else if (u == 0)
{
   DP[i][u] = 0;
}

这应该是因为你可以用 1 美分硬币以一种可能的方式DP[i][u]=1产生任何价值。i即拿 5 美分，你将拿 5 个 1 美分硬币，这是总共赚 5 美分的一种方法。

-----

顺便说一句，在您使用 count 方法的第一种方法中，您是否有这个：

if (DP[n][m - 1] == -1 || DP[n - s[m]][m] == -1)
{
  return count(n, m - 1) + count(n - s[m], m);
}

或这个：

if (DP[n][m - 1] == -1 || DP[n - s[m]][m] == -1)
{
    return DP[n][m] = count(n, m - 1) + count(n - s[m], m);
}

如果您没有记住已经计算的结果，那么这个记忆检查if (DP[n][m - 1] == -1 || DP[n - s[m]][m] == -1)将永远不会起作用，这可能是您的第一种方法太慢的原因:-？

于 2013-04-16T16:53:22.967 回答