需要木刻递归建议

Question

给你一根长度为 'n' 的原木。日志上有“m”标记。原木必须在每个标记处切割。切割成本等于被切割原木的长度。给定这样一根原木，求出最小的切割成本。

我的部分解决方案是使用递归：当我在标记数组中按顺序进行时，即从第 0 次切割到数组切割结束时，我能够获得成本。然而，当我们不按顺序切割时，我对如何为序列编写代码感到困惑，即在随机序列中，例如代码可以解释切割不按顺序的情况，并为所有这些情况取最大值。

一种解决方案是对标记数组进行所有排列。为所有排列调用 woodcut 函数并取最大值，但这似乎是一种幼稚的方法。

有什么建议吗？

marking = [2, 4] (切点)

int woodcut(length, cut_point, index){
    if (cut_point > length)
            return INFINITY
    first_half = cut_point;
    second_half = length - cut_point
    if (markings[index++] == exist) {
            if (next_cut_point > first)
                    cost = length + woodcut(second_half, next_cut_point-first)
            else    
                    cost = length + woodcut(first_half, next_cut_point)  
    } else if (index >= sizeof(markings))
            return cost;
}

http://www.careercup.com/question?id=5188262471663616

在查找答案并得到一些慷慨的人的帮助后，我编写了以下解决方案：

    #include <stdio.h>

    int min(int a, int b)
    {
            return a>b?b:a;
    }

    int min_cut(int first, int last, int size, int *cuts)
    {
            int i;
            unsigned int min_cost = 1U<<30;
            /* there are no cuts */
            if (size == 2)
                    return 0;
            /* there is only one cut between the end points */
            if (size == 3)
                    return last - first;
            /* cut at all the positions and take minimum of all */
            for (i=1;i<size;i++) {
                    if (cuts[i] > first && cuts[i] < last) {
                            int cost = last-first + min_cut(first, cuts[i], i+1, cuts) +
                                                    min_cut(cuts[i], last, size - i, cuts);
                            min_cost = min(cost, min_cost);
                    }
            }
            return min_cost;
    }

    int main()
    {
            int cuts[] = {0, 2, 4, 7, 10};
            int size = sizeof(cuts)/sizeof(cuts[0]);
            printf("%d", min_cut(cuts[0], cuts[size-1], size, cuts));
            return 0;
    }

Answer 1

方法一：

首先编写一个简单的递归函数，计算从第 i 标记到第 j 标记切割成块的最便宜成本。通过将第一次切割的成本加上切割两侧的最小成本的所有可能的第一次切割的最小值来做到这一点。

记忆这个函数，所以它很有效。

方法二：计算一个table个值，用于计算从第i分到j分的最便宜的切割成本。使用标记数量的外循环 i 和 j 是分开的，然后使用 i 的内循环，然后是可能位置的非常内循环来进行第一次切割.

两种方法都有效。两者都是 O(m*m*m) 我通常会选择方法 A.

Answer 2

这种情况类似于分而治之的排序。以快速排序为例：

有一个分区步骤需要对数组进行线性传递以将其分成两个子数组。同样，切割一根原木的成本等于它的长度。
然后有一个递归步骤，其中每个子数组被递归排序。同样，您必须递归地继续切割日志被切割成的两块中的每一块，直到切割完所有标记。

Quicksort 在最好的情况下当然是 O(n log n)，当每个分区步骤（基本情况除外）将数组分成两个大小几乎相等的子数组时，就会发生这种情况。因此，您需要做的就是找到最靠近中间的标记，"cut"那里的日志，然后递归。

Answer 3

动态规划。复杂度 O(m^3)。 python 中的解决方案。输入为标记位置的有序列表，最后一项为log的长度：

def log_cut(m):
  def _log_cut(a, b):
    if mat[a][b]==None:
      s=0
      min_v=None
      for i in range(a+1, b):
         v=_log_cut(a, i)+_log_cut(i, b)
         if min_v==None or v<min_v:
           min_v=v
      if min_v!=None:
        s=min_v+m[b-1]
        if a>0:
          s-=m[a-1]
      mat[a][b]=s
    return mat[a][b]

  mat=[[None for i in range(len(m)+1)] for j in range(len(m)+1)]
  s=_log_cut(0, len(m))
  return s

需要木刻递归建议

need woodcutting recursion advice

algorithm

recursion

dynamic-programming