0

我正在处理一个问题，试图制作一种递归方法来测试所有可能的组合并向我展示“最便宜”的组合。

任务是：

  • 我有一个 Array[n] 数字，它是动态分配和填充的。{1, 3, 4, 2} 例如。数组定义为
    int *array;
  • 我喜欢数组的大小并放入变量 Size。
  • 数组中的每 2 个数字表示一个段的顶部和底部，因此在这种情况下，数组有 3 个段。这些段是：A = 1 3 ，B = 3 4 ，C = 4 2 。
  • 我必须按照他们的顺序加入他们。我可以从最后两个开始加入到第一个，或者我可以从中心到两侧开始，但我必须选择“最便宜”的方式。
  • 每次我加入两个段： A = 1 3 和 B = 3 4 。我这样计算它的成本：(1 * 4) + 3。我将段末端的数字相乘，然后将总和与段之间的数字相乘。
  • 输入将始终是 2 个或更多段，表示数组中的 3 个或更多数字。

实际上我需要它做的是：

For two segments: array= "1 2 3"
A={1,2},B={2,3} ---- (1*3)+2 -> Cost = 5

For three segments: array= "30 20 25 10"
A={30,20},B={20,25},C={25,10} ----
case1 - [(30*25)+20] + [(30*10)+25] -> Cost = 1095
case2 - [(20*10)+25] + [(30*10)+20] /> Cost = 545

所以我们可以清楚地看到第二个成本更好，所以我们返回那个值。对于更多的段，计算的数量将急剧增加，但这对于我的需要来说是可以的。

我已经以不同的方式尝试了很多次，但我对所有的指针都感到困惑，而且我对递归函数也不擅长。我不知道我是否足够具体，如果有不清楚的地方，我会很乐意解释。

我当然不需要整个代码，也许会得到一些解释或关于如何做到这一点的想法:)

4

1 回答 1

0

让我们的数字A数组，第 j 个元素和 A 的子数组，第 i 个到第 k 个元素，包括。索引从 0 开始计数，因此. 加入操作的结果是什么？例如有两个部分，我正确地假设连接在一起会是？nA[j]A[i,k]A = A[0, n-1]A = { 1, 2, 3 }1,22,31,3

由于每个连接都将 A 分成两部分，因此您可以通过测试 的所有可能连接（A即n-2可能性）来递归，选择成本最低的连接。也许这个方程给你一个想法。

/* cost of join two segments of A ending respective starting at j */
cost(A,j) = ( A[j-1]*A[j+1] ) + A[j]

 /* minmal cost of joining(A) when joining at j */
mincost(A,j) = mincost( A[0,j-1] ) + cost(A,j) + mincost( A[j+1,n-1] )

/* test all possible join, use minimal one */
mincost(A) = min[j]: mincost(A,j)

结束递归时n=3，使用cost(A,1).

对于可用的算法，您可能必须缓存mincost(A[x,y])这称为动态编程。

在 C A[j]中可以翻译为*(A+j)where asA[i,k]不直接对应一个 C 构造，但可以大致翻译为如下

 struct Array { 
          int * A; 
          int index_first;
          int index_last;
 };
于 2012-11-28T16:03:21.537 回答