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

只要不超过您的总和,您就可以重复数字。哪种方式最好编程?

4

7 回答 7

8

这是对更改生成问题的轻微修改。你应该可以找到很多关于这个问题的论文,一个动态编程解决方案只需要不超过 20 行代码。

http://en.wikipedia.org/wiki/Change-making_problem

于 2009-09-29T00:50:39.147 回答
2

这些被称为数字的分区,您的问题似乎强加了您可以在分区中使用哪些数字的约束。

于 2009-09-29T05:18:57.117 回答
2

这也可能有帮助:动态编程:组合和问题

于 2009-09-29T01:26:37.070 回答
2

这个问题被称为“双重限制整数分区”。如果“允许”总和为 5 的数字来自集合 V,则称为“乘法受限整数分区”。Riha 和 James 有一篇论文:“算法 29:双重和多重受限分区的有效算法”计算第 16 卷,第 1-2 期,第 163-168 页(1976 年)。你应该阅读那篇论文并实现他们的算法。了解如何做到这一点将使您能够针对特定问题实施独特的优化。

于 2012-09-25T17:39:05.977 回答
0
    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;
    }
于 2010-12-30T13:29:23.557 回答
0

我会首先从最高数字开始递归地进行。然后,每次从最高级别开始,进入与数字一样多的级别。一旦累积水平超过您的值,就下降到下一个数字。如果仍然太大(或太小),请立即返回一个级别并将其减少到下一个数字,然后再从顶部开始到下一个更深的级别。

于 2009-09-29T00:46:36.153 回答
-1

您可以使用以下代码..它会根据需要为您提供准确的答案..

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);

}
于 2013-07-10T12:38:27.420 回答