不正确的递归方法来查找硬币组合以产生给定的零钱 [英] Incorrect Recursive approach to finding combinations of coins to produce given change

问题描述

我最近正在做一个项目欧拉问题（即＃31），该问题基本上是找出使用集合{1,2,5,10,20,50,100,200}的元素可以求出200种方法的总和。

我使用的想法是：求和N的方式等于

（求和Nk的方式数）*（求和k的方式数），求和k的所有可能值。

我意识到这种方法是错误的，即由于它创建了多个重复计数。我试图调整公式以避免重复，但无济于事。我正在寻求关于以下方面的堆栈溢出问题的智慧：

1. 我的递归方法是否与 correct 子问题有关解决


2. 如果存在一个，什么是消除重复的有效方法


3. 我们应该如何处理递归问题，以便我们关注正确的子问题？我们选择了正确（或不正确）子问题的指标有哪些？

解决方案

在尝试避免重复排列时，一种在大多数情况下有效的简单策略是仅创建上升或下降序列。

在您的示例中，如果选择一个值，然后用整个集合递归，您将得到重复的序列，例如 50,50,100 和 50,100,50 和 100,50,50 。但是，如果递归使用下一个值应等于或小于当前选定值的规则，则在这三个值中，您只会得到序列 100,50,50 。

因此，仅计算唯一组合的算法为：

  function uniqueCombinations（set，target，previous）{
对于集合中的所有值不大于先前的{
，如果值等于目标{
增量计数
} 
（如果值小于目标{{
 uniqueCombinations（set，target-value，value）
} 
} 
} 
 
 uniqueCombinations（[1 ，2,5,10,20,50,100,200]，200，200）
  

您也可以创建在每次递归之前复制该集合的副本，并从中删除您不想重复的元素。

上升/下降序列方法也可用于迭代。假设您要查找三个字母的所有唯一组合。此算法将打印类似 a，c，e 的结果，但不会打印 a，e，c 或 e，a，c ：

  for letter1是'a'到'x'{ 
代表letter2是字母1到y之后的第一个字母{
代表letter3是字母2到'z'之后的第一个字母{
 print [letter1，letter2，letter3] 
} 
} 
} 
  

I was recently doing a project euler problem (namely #31) which was basically finding out how many ways we can sum to 200 using elements of the set {1,2,5,10,20,50,100,200}.

The idea that I used was this: the number of ways to sum to N is equal to

(the number of ways to sum N-k) * (number of ways to sum k), summed over all possible values of k.

I realized that this approach is WRONG, namely due to the fact that it creates several several duplicate counts. I have tried to adjust the formula to avoid duplicates, but to no avail. I am seeking the wisdom of stack overflowers regarding:

1. whether my recursive approach is concerned with the correct subproblem to solve
2. If there exists one, what would be an effective way to eliminate duplicates
3. how should we approach recursive problems such that we are concerned with the correct subproblem? what are some indicators that we've chosen a correct (or incorrect) subproblem?

解决方案

When trying to avoid duplicate permutations, a straightforward strategy that works in most cases is to only create rising or falling sequences.

In your example, if you pick a value and then recurse with the whole set, you will get duplicate sequences like 50,50,100 and 50,100,50 and 100,50,50. However, if you recurse with the rule that the next value should be equal to or smaller than the currently selected value, out of those three you will only get the sequence 100,50,50.

So an algorithm that counts only unique combinations would be e.g.:

function uniqueCombinations(set, target, previous) {
    for all values in set not greater than previous {
        if value equals target {
            increment count
        }
        if value is smaller than target {
            uniqueCombinations(set, target - value, value)
        }
    }
}

uniqueCombinations([1,2,5,10,20,50,100,200], 200, 200)

Alternatively, you can create a copy of the set before every recursion, and remove the elements from it that you don't want repeated.

The rising/falling sequence method also works with iterations. Let's say you want to find all unique combinations of three letters. This algorithm will print results like a,c,e, but not a,e,c or e,a,c:

for letter1 is 'a' to 'x' {
    for letter2 is first letter after letter1 to 'y' {
        for letter3 is first letter after letter2 to 'z' {
            print [letter1,letter2,letter3]
        }
    }
}

这篇关于不正确的递归方法来查找硬币组合以产生给定的零钱的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！