生成所有可能的组合的代码。
生成所有可能的组合的代码。
提问于 2014-12-05 01:49:05
如果我有3个苹果和2个桶，我可以把它们组织如下：
- A桶1个苹果，B桶2个苹果
- A桶2个苹果，B桶1个苹果
- A桶3个苹果，B桶0个苹果
- B桶3个苹果，A桶0个苹果
等等。
当苹果的数量可以是任何数字，桶的数量也可以是任何数字时，我正试图编写某种程序来为我生成这样的组合。我的直觉告诉我，会有一些递归，但，我甚至不能开始。有人能给我指明正确的方向吗？
回答 2
Stack Overflow用户
发布于 2014-12-05 02:35:11
是的，递归可以用来解决这个问题。
提示:如果您有M苹果和N桶，那么可以通过将m <= M苹果放入第一个桶中，然后找到(M - m)苹果和N - 1桶子问题的所有解决方案来找到解决方案的一个子集。
Stack Overflow用户
发布于 2014-12-05 03:22:53
是的，您当然可以使用递归，它可以通过将上下文保存在堆中来简化事情。但这不是绝对必要的。
这里有一些(不太有效，而且缺少了很多东西)的psuedo代码，如果您喜欢这种方法，可以使用interation为您提供起点。下面的算法看起来有点不直观，但如果你仔细考虑，你会发现它是有效的。我已经试过了，它运行得很好，所以如果你被卡住了，请告诉我，我会发布一些工作代码。您还可能希望尝试递归版本和迭代版本，看看哪个版本对您更有意义。
put all apples in first bucket
while (true) {
add the solution to the list
firstNonEmptyBucket = find first bucket with any apples;
if (firstNonEmptyBucket is the last bucket)
break - you are finished
shift 1 apple from firstNonEmptyBucket to next bucket
if (firstNonEmptyBucket is not the first bucket)
shift all apples from firstNonEmptyBucket to previous bucket
}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/27307490
复制相关文章
相似问题
腾讯云开发者
