首页 文章

硬币变化（动态编程）

提问于
浏览 次
4

我有一个关于硬币变化问题的问题，我们不仅需要打印用给定硬币面额更改$ n的方法的数量，例如{1,5,10,25}，而且还打印方式

例如，如果目标= $ 50，并且硬币是 {1,5,10,25} ，那么实际使用硬币获得目标的方法是

  • 2×25美元

  • 1×25美元2×10美元1×5美元

  • 等

我们可以解决这个问题的最佳时间复杂度是多少？我试图修改硬币更改问题的动态编程解决方案，我们只需要多种方式而不是实际方式

我无法搞清楚时间的复杂性 . 我确实使用了记忆，因此我不必为给定的硬币和总和值再次解决同样的问题，但我们仍需要遍历所有解决方案并打印它们 . 所以时间复杂度肯定超过O（ns），其中n是硬币数，s是目标它是指数吗？任何帮助都感激不尽

algorithm time-complexity dynamic-programming

3 回答

  • 0

    打印组合

    def coin_change_solutions(coins, S):
  # create an S x N table for memoization
  N = len(coins)
  sols = [[[] for n in xrange(N + 1)] for s in xrange(S + 1)]
  for n in range(0, N + 1):
    sols[0][n].append([])

  # fill table using bottom-up dynamic programming
  for s in range(1, S+1):
    for n in range(1, N+1):
      without_last = sols[s][n - 1]
      if (coins[n - 1] <= s):
          with_last = [list(sol) + [coins[n-1]] for sol in sols[s - coins[n - 1]][n]]
      else:
          with_last = []
      sols[s][n] = without_last + with_last

  return sols[S][N]


print coin_change_solutions([1,2], 4)
# => [[1, 1, 1, 1], [1, 1, 2], [2, 2]]

    • without ：我们不需要使用最后一枚硬币来计算金额 . 通过递归 solution[s][n-1] 直接找到所有硬币解决方案 . 我们将所有这些硬币组合复制到 with_last_sols .

    • with ：我们确实需要使用最后一枚硬币 . 所以硬币必须在我们的解决方案中 . 其余的硬币通过 sol[s - coins[n - 1]][n] 递归发现 . 阅读此条目将为我们提供许多可能的选择，以确定剩余的硬币应该是什么 . 对于每个可能的选择 sol ，我们追加最后一枚硬币 coin[n - 1] ：

    # For example, suppose target is s = 4
# We're finding solutions that use the last coin.
# Suppose the last coin has a value of 2:
#
# find possible combinations that add up to 4 - 2 = 2: 
# ===> [[1,1], [2]] 
# then for each combination, add the last coin 
# so that the combination adds up to 4)
# ===> [[1,1,2], [2,2]]

    通过采用第一种情况和第二种情况的组合并连接两个列表，找到最终的组合列表 .

    without_last_sols = [[1,1,1,1]]
with_last_sols = [[1,1,2], [2,2]]
without_last_sols + with_last_sols = [[1,1,1,1], [1,1,2], [2,2]]

    时间复杂性

    在最坏的情况下，我们有一个硬币套装，所有硬币从1到n：硬币= [1,2,3,4，...，n] - 可能的硬币总和组合数量，num解决方案，等于s，p（s）的integer partitions的数量 . 可以看出，整数分区的数量p（s）增长exponentially .
    因此，num solutions = p（s）= O（2 ^ s） . 任何解决方案都必须至少具有此功能，以便它可以打印出所有这些可能的解决方案 . 因此，问题本质上是指数级的 .

    我们有两个循环：一个循环用于s，另一个循环用于n .
    对于每个s和n，我们计算 sols[s][n] ：

    • without ：我们看一下 sol[s - coins[n - 1]][n] 中的O（2 ^ s）组合 . 对于每种组合，我们在O（n）时间内复制它 . 总的来说这需要：O（n×2 ^ s）时间 .

    • with ：我们查看 sol[s][n] 中的所有O（2 ^ s）组合 . 对于每个组合列表 sol ，我们在O（n）时间内创建该新列表的副本，然后附加最后一个硬币 . 总的来说，这种情况需要O（n×2 ^ s） .

    因此，时间复杂度为O（s×n）×O（n2 ^ s n2 ^ s）= O（s×n ^ 2×2 ^ s） .

    空间复杂性

    空间复杂度为O（s×n ^ 2×2 ^ s），因为我们有×n表，每个条目存储O（2 ^ s）个可能的组合，（例如 [[1, 1, 1, 1], [1, 1, 2], [2, 2]] ），每个组合，（例如 [1,1,1,1] ） O（n）空间 .

    回复于
  • 1

    我倾向于做的是递归地解决问题，然后从那里构建一个memoization解决方案 .

    从递归的方法开始，方法很简单，从目标中选择硬币减去并且不要选择硬币 .

    当你选择一个硬币时，你将它添加到矢量或列表中，当你不选择一个硬币时，你弹出你之前添加的硬币 . 代码看起来像：

    void print(vector<int>& coinsUsed)
{
    for(auto c : coinsUsed)
    {
        cout << c << ",";
    }
    cout << endl;
}

int helper(vector<int>& coins, int target, int index, vector<int>& coinsUsed)
{
    if (index >= coins.size() || target < 0) return 0;

    if (target == 0)
    {
        print(coinsUsed);
        return 1;
    }

    coinsUsed.push_back(coins[index]);
    int with = helper(coins, target - coins[index], index, coinsUsed);

    coinsUsed.pop_back();
    int without = helper(coins, target, index + 1, coinsUsed);

    return with + without;
}

int coinChange(vector<int>& coins, int target)
{
    vector<int> coinsUsed;
    return helper(coins, target, 0, coinsUsed);
}

    你可以这样称呼：

    vector<int> coins = {1,5,10,25};
cout << "Total Ways:" << coinChange(coins, 10);

    因此，这将为您提供总路径以及在此过程中用于到达存储在 coinsUsed 中的目标的硬币 . 您现在可以通过将传入的值存储在缓存中来随意记住它 .

    递归解的时间复杂度是指数的 .

    链接到正在运行的程序：http://coliru.stacked-crooked.com/a/5ef0ed76b7a496fe

    回复于
  • 0

    让d_i为面额，硬币的 Value 为美分 . 在你的例子中，d_i = {1,5,10,25} . 设k是面额（硬币）的数量，这里k = 4 .

    我们将使用2D数组numberOfCoins [1..k] [0..n]来确定进行更改所需的最小硬币 number . 最佳解决方案由：

    numberOfCoins[k][n] = min(numberOfCoins[i − 1][j], numberOfCoins[i][j − d_i] + 1)

    上面的等式代表了这样一个事实，即要 Build 一个最优解，我们要么不使用d_i，所以我们需要使用一个较小的硬币（这就是为什么我在下面递减）：

    numberOfCoins[i][j] = numberOfCoins[i − 1][j]   // eq1

    或者我们使用d_i，所以我们将所需硬币数加1，然后减去d_i（我们刚刚使用的硬币的值）：

    numberOfCoins[i][j] = numberOfCoins[i][j − d_i] + 1   // eq2

    时间复杂度是O（kn）但是在k很小的情况下，就像你的例子中的情况一样，我们有O（4n）= O（n） .

    我们将使用另一个2D数组，coinUsed，具有与numberOfCoins相同的尺寸，以标记使用哪些硬币 . 每个条目要么告诉我们我们没有在coinUsed [i] [j]中使用硬币，在该位置设置“^”（这对应于eq1） . 或者我们通过在该位置设置“<”来标记硬币的使用（对应于eq2） .

    在算法运行时，可以构建两个阵列 . 我们只会在内循环中有更多的指令，因此时间复杂度构建两个数组仍然是O（kn） .

    为了打印解决方案，我们需要迭代，在更糟糕的情况下，k n 1个元素 . 例如，当最优解决方案使用所有1美分面额时 . 但请注意，打印是在构建之后完成的，因此总体时间复杂度为O（kn）O（k n 1） . 如前所述，如果k很小，则复杂度为O（kn）O（kn 1）= O（kn）O（n 1）= O（kn）O（n）= O（（k 1）n）= O（ N） .

    回复于

相关问题