确定可能的项目组的算法
我正试图这样做，它正在吃我。 我知道这不复杂。 我有很多项目，这个数字可以等于或大于3。 然后我需要确定将完成总计的项目组的可能组合。 唯一的限制是团体应该有三件或更多件，不超过（但包括）七件。
例如：
如果我有7个项目，那么我可以拥有这些可能的组：
- 1组7项。
- 1组4项和1组3项。
如果我有12个项目，我可以拥有这些可能的组：
- 4组3项。
- 3组4项。
- 2组6项。
- 1组7项+ 1组5项。
- 2组3组和1组6项。
- 1组3组，1组4组和1组五项。
- …
我考虑了递归并开始实现算法。 它显然不起作用。 我吮吸递归。 很多。
//Instance Fields public List<ArrayList> options; //Method that will generate the options. The different options are //stored in a list of "option". An individual option will store a list of //strings with the individual groups. public void generateOptions(int items, ArrayList currentOption){ //If the current option is null, then create a new option. if(currentOption == null){ currentOption = new ArrayList(); } if(items < 3){ //If the number of items is less than three then it doesn't comply with the //requirements (teams should be more or equal than three. currentOption.add("1 group of "+items+" items"); options.add(currentOption); } else{ //I can make groups of 3,4,5,6 and 7 items. for(int i = 3;i=3){ currentOption.add("1 group of "+i+" items"); generateOptions(items-i,currentOption); } } } } } 谢谢你的帮助！！！
这是一个算法（用C ++表示）来解决问题的更一般版本，在每个分区中可能出现的加数上有任意上限和下限：
#include #include using namespace std; typedef vector Partition; typedef vector Partition_list; // Count and return all partitions of an integer N using only // addends between min and max inclusive. int p(int min, int max, int n, Partition_list &v) { if (min > max) return 0; if (min > n) return 0; if (min == n) { Partition vtemp(1,min); v.push_back(vtemp); return 1; } else { Partition_list part1,part2; int p1 = p(min+1,max,n,part1); int p2 = p(min,max,n-min,part2); v.insert(v.end(),part1.begin(),part1.end()); for(int i=0; i < p2; i++) { part2[i].push_back(min); } v.insert(v.end(),part2.begin(),part2.end()); return p1+p2; } } void print_partition(Partition &p) { for(int i=0; i < p.size(); i++) { cout << p[i] << ' '; } cout << "\n"; } void print_partition_list(Partition_list &pl) { for(int i = 0; i < pl.size(); i++) { print_partition(pl[i]); } } int main(int argc, char **argv) { Partition_list v_master; int n = atoi(argv[1]); int min = atoi(argv[2]); int max = atoi(argv[3]); int count = p(min,max,n,v_master); cout << count << " partitions of " << n << " with min " << min ; cout << " and max " << max << ":\n" ; print_partition_list(v_master); }
还有一些示例输出：
$ ./partitions 12 3 7 6 partitions of 12 with min 3 and max 7: 6 6 7 5 4 4 4 5 4 3 6 3 3 3 3 3 3 $ ./partitions 50 10 20 38 partitions of 50 with min 10 and max 20: 17 17 16 18 16 16 18 17 15 19 16 15 20 15 15 18 18 14 19 17 14 20 16 14 19 18 13 20 17 13 19 19 12 20 18 12 13 13 12 12 14 12 12 12 20 19 11 13 13 13 11 14 13 12 11 15 12 12 11 14 14 11 11 15 13 11 11 16 12 11 11 17 11 11 11 20 20 10 14 13 13 10 14 14 12 10 15 13 12 10 16 12 12 10 15 14 11 10 16 13 11 10 17 12 11 10 18 11 11 10 15 15 10 10 16 14 10 10 17 13 10 10 18 12 10 10 19 11 10 10 20 10 10 10 10 10 10 10 10
它可以通过递归完成。 你不是说你是否只想要可能性或实际可能性。
你要做的一件事是避免重复，这意味着不要将4和3算作3和4.一种方法是创建非下降组大小的序列。
可能最好的数据结构是树：
root +- 12 +- 9 | +- 3 +- 8 | +- 4 +- 7 | +- 5 +- 6 | +- 6 | +- 3 | +- 3 +- 5 | +- 4 | +- 3 +- 4 | +- 4 | +- 4 +- 3 +- 3 +- 3 +- 3
然后，要查找组合数，您只需计算叶节点。 要找到实际组合，您只需走树。
构建这样一棵树的算法是这样的：
- 函数buildTree（int size，int minSize，Tree root）
- 从
size到minSize计算i; - 使用值
i创建当前节点的子节点; - 对于从
minSize到i每个小于或等于i- 创建一个值为
j的新子j - 调用`buildTree（j，minSize，new node）
- 创建一个值为
或者非常接近的东西。
我认为树是思考它的最佳方式，但你可以使用递归来构建一个树而不需要明确地创建树。 您可以将根视为总数。 使用大小为3-7的组，您需要找到总计达总数的组的组合。
您可以使用0组7组，1组7组，2组7组等。对于每个值，您可以使用0组6,1组6，等等。树的第一级将表示如何使用了很多7个。 第二个级别是使用了多少6个等等。当你使用x 7时，你需要弄清楚你可以使用多少组合6，5，4和3来总和（sum-x * 7） ，等等每个较低级别（递归调用）。
你的树总是有5个级别。
使用递归来构建树，这里有一个小的Python代码示例（没有尝试修剪树，它将探索整个事物）。
MIN = 3 MAX = 7 def findComb(remaining, start, path): times = remaining/start if start == MIN: if remaining % MIN == 0: print "%s, %d %d's" % (path[1:], times, start) return for i in range(0, times+1): findComb(remaining- (i*start), start-1, "%s, %d %d's" % (path, i, start)) findComb(12, MAX, "")
这输出：
0 7's, 0 6's, 0 5's, 0 4's, 4 3's 0 7's, 0 6's, 0 5's, 3 4's, 0 3's 0 7's, 0 6's, 1 5's, 1 4's, 1 3's 0 7's, 1 6's, 0 5's, 0 4's, 2 3's 0 7's, 2 6's, 0 5's, 0 4's, 0 3's 1 7's, 0 6's, 1 5's, 0 4's, 0 3's
这将是n的分区数，它只包含集合中的整数[3,7]
类似于常规分区问题（其中元素可以是任何正整数）：
http://www.research.att.com/~njas/sequences/A000041
我没有看到完全匹配此约束的现有数字序列，但您可以像这样计算组（在python中）。 这可以采取任意范围（在这种情况下为[3,7]）并计算所有a，b，c，d，e（3 * a + 4 * b + 5 * c + 6 * d + 7 * e）总和为n的序列。
import sys # All partitions for a particular n: def groups(n, base, minBase, sum, sets, group = []): c = 0; i = (n - sum) / base while i >= 0: s = sum + base * i if s == n: sets.append(group + [i]); c = c + 1 elif s < n and base > minBase: c = c + groups(n, base - 1, minBase, s, sets, (group + [i])) i = i - 1 return c # Partitions for each n in [1,maxNum] def run(maxNum): for i in xrange(1, maxNum + 1): sets = []; maxBase = 7; minBase = 3 n = groups(i, maxBase, minBase, 0, sets) print ' %d has %d groups:\n' % (i, n) for g in sets: x = len(g) - 1 sys.stdout.write(' ') while x >= 0: if g[x] > 0: if x < len(g) - 1: sys.stdout.write(' + ') sys.stdout.write('(%d * %d)' % (maxBase - x, g[x])) x = x - 1 print '' if len(sets): print '' run(40)
你有：
1 has 0 groups: 2 has 0 groups: 3 has 1 groups: (3 * 1) 4 has 1 groups: (4 * 1) 5 has 1 groups: (5 * 1) 6 has 2 groups: (6 * 1) (3 * 2) 7 has 2 groups: (7 * 1) (3 * 1) + (4 * 1) 8 has 2 groups: (3 * 1) + (5 * 1) (4 * 2) 9 has 3 groups: (3 * 1) + (6 * 1) (4 * 1) + (5 * 1) (3 * 3) 10 has 4 groups: (3 * 1) + (7 * 1) (4 * 1) + (6 * 1) (5 * 2) (3 * 2) + (4 * 1) 11 has 4 groups: (4 * 1) + (7 * 1) (5 * 1) + (6 * 1) (3 * 2) + (5 * 1) (3 * 1) + (4 * 2) 12 has 6 groups: (5 * 1) + (7 * 1) (6 * 2) (3 * 2) + (6 * 1) (3 * 1) + (4 * 1) + (5 * 1) (4 * 3) (3 * 4) 13 has 6 groups: (6 * 1) + (7 * 1) (3 * 2) + (7 * 1) (3 * 1) + (4 * 1) + (6 * 1) (3 * 1) + (5 * 2) (4 * 2) + (5 * 1) (3 * 3) + (4 * 1) 14 has 7 groups: (7 * 2) (3 * 1) + (4 * 1) + (7 * 1) (3 * 1) + (5 * 1) + (6 * 1) (4 * 2) + (6 * 1) (4 * 1) + (5 * 2) (3 * 3) + (5 * 1) (3 * 2) + (4 * 2) 15 has 9 groups: (3 * 1) + (5 * 1) + (7 * 1) (4 * 2) + (7 * 1) (3 * 1) + (6 * 2) (4 * 1) + (5 * 1) + (6 * 1) (3 * 3) + (6 * 1) (5 * 3) (3 * 2) + (4 * 1) + (5 * 1) (3 * 1) + (4 * 3) (3 * 5)
或@ Cletus的出色解决方案
在伪代码中：
List results; void YourAnswer(int n) { GeneratePossiblities("", [3, 4, 5, 6, 7], n); } void GeneratePossibilities(String partialResult, List buildingBlocks, int n) { if (n == 0) { // We have a solution results.Add(partialResult); } else if (buildingBlocks.IsEmpty()) { // Dead-end: there is no solution that starts with the partial result we have and contains only the remaining building blocks return; } else { int first = buildingBlocks.First(); buildingBlocks.PopFirst(); for (int i = 0, i < n/first; i++) { GeneratePossibilities(partialResult + " " + i + "groups of " + first, buildingBlocks, n - i * first); } } }
前两个案例非常简单。 第三个，你弄清楚（例如）有多少个大小为3的组 - 可以是0到n / 3之间的任何数字，然后用[4,5,6,7]等递归函数。
您所描述的是分区函数的一般版本。
已经给出的算法是非常复杂的，这里是一个更简单的算法（在伪代码中，我会留给你翻译成Java :) ）
p(min, n): if min > n: return 0 if min = n: return 1 return p(min+1, n) + p(min, n-min)