我有一个像 1,2,3 这样的数字列表,我想找到总和为特定数字(如 5)的所有组合模式。例如:
Sum=5
Numbers:1,2,3
Patterns:
1 1 1 1 1
1 1 1 2
1 1 3
1 2 2
2 3
只要不超过您的总和,您就可以重复数字。哪种方式最好编程?
我有一个像 1,2,3 这样的数字列表,我想找到总和为特定数字(如 5)的所有组合模式。例如:
Sum=5
Numbers:1,2,3
Patterns:
1 1 1 1 1
1 1 1 2
1 1 3
1 2 2
2 3
只要不超过您的总和,您就可以重复数字。哪种方式最好编程?
这是对更改生成问题的轻微修改。你应该可以找到很多关于这个问题的论文,一个动态编程解决方案只需要不超过 20 行代码。
这些被称为数字的分区,您的问题似乎强加了您可以在分区中使用哪些数字的约束。
这也可能有帮助:动态编程:组合和问题
这个问题被称为“双重限制整数分区”。如果“允许”总和为 5 的数字来自集合 V,则称为“乘法受限整数分区”。Riha 和 James 有一篇论文:“算法 29:双重和多重受限分区的有效算法”计算第 16 卷,第 1-2 期,第 163-168 页(1976 年)。你应该阅读那篇论文并实现他们的算法。了解如何做到这一点将使您能够针对特定问题实施独特的优化。
public static List<List<string>> Partition(int n, int max, string prefix)
{
if (n == 0)
{
_results.Add(prefix.Split(new char[] { ',' }).ToList());
}
for (int i = Math.Min(max, n); i >= 1; i--)
{
Partition(n - i, i, prefix + "," + i);
}
return _results;
}
我会首先从最高数字开始递归地进行。然后,每次从最高级别开始,进入与数字一样多的级别。一旦累积水平超过您的值,就下降到下一个数字。如果仍然太大(或太小),请立即返回一个级别并将其减少到下一个数字,然后再从顶部开始到下一个更深的级别。
您可以使用以下代码..它会根据需要为您提供准确的答案..
void print(int n, int * a)
{
int i ;
for (i = 0; i <= n; i++)
{
printf("%d", a[i]);
}
printf("\n");
}
void integerPartition(int n, int * a, int level)
{
int first;
int i;
if (n < 1)
return ;
a[level] = n;
print(level, a);
first = (level == 0) ? 1 : a[level-1];
for(i = first; i <= n / 2; i++)
{
a[level] = i;
integerPartition(n - i, a, level + 1);
}
}
int main()
{
int n = 10;
int * a = (int * ) malloc(sizeof(int) * n);
integerPartition (n, a, 0);
return(0);
}