9

我一直在研究这本书中的以下问题。

某种字符串处理语言提供了一种将字符串分成两部分的原始操作。由于此操作涉及复制原始字符串，因此无论剪切的位置如何，长度为 n 的字符串都需要 n 个单位时间。现在假设你想把一个字符串分成很多块。休息的顺序会影响总运行时间。例如，如果你想在位置 3 和 10 剪切一个 20 个字符的字符串，那么在位置 3 进行第一次剪切会产生 20+17=37 的总成本，而首先执行位置 10 的成本会更好 20+ 10=30。

我需要一个动态编程算法，给定 m 个切割，找到将一个字符串切割成 m+1 个片段的最小成本。

4

4 回答 4

3

在我看来，分而治之的方法是解决这类问题的最佳方法。这是该算法的Java实现：

注意：数组m应按升序排序（使用Arrays.sort(m);）

public int findMinCutCost(int[] m, int n) {
   int cost = n * m.length;
   for (int i=0; i<m.length; i++) {
      cost = Math.min(findMinCutCostImpl(m, n, i), cost);
   }
   return cost;
}

private int findMinCutCostImpl(int[] m, int n, int i) {
   if (m.length == 1) return n;
   int cl = 0, cr = 0;
   if (i > 0) {
      cl = Integer.MAX_VALUE;
      int[] ml = Arrays.copyOfRange(m, 0, i);
      int nl = m[i];
      for (int j=0; j<ml.length; j++) {
         cl = Math.min(findMinCutCostImpl(ml, nl, j), cl);
      }
   }
   if (i < m.length - 1) {
      cr = Integer.MAX_VALUE;
      int[] mr = Arrays.copyOfRange(m, i + 1, m.length);
      int nr = n - m[i];
      for (int j=0; j<mr.length; j++) {
         mr[j] = mr[j] - m[i];
      }
      for (int j=0; j<mr.length; j++) {
         cr = Math.min(findMinCutCostImpl(mr, nr, j), cr);
      }
   }
   return n + cl + cr;
}

例如 ：

 int n = 20;
 int[] m = new int[] { 10, 3 };

 System.out.println(findMinCutCost(m, n));

将打印30

**编辑**

我已经实施了另外两种方法来回答问题中的问题。

1. 中切近似

这种方法总是递归地切割最大的块。结果并不总是最好的解决方案，但提供了不可忽略的增益（在我的测试中大约为 +100000% 增益），与最佳成本的最小切割损失差异可忽略不计。

public int findMinCutCost2(int[] m, int n) {
   if (m.length == 0) return 0;
   if (m.length == 1) return n;
      float half = n/2f;
      int bestIndex = 0;
      for (int i=1; i<m.length; i++) {
         if (Math.abs(half - m[bestIndex]) > Math.abs(half - m[i])) {
            bestIndex = i;
         }
      }
      int cl = 0, cr = 0;
      if (bestIndex > 0) {
         int[] ml = Arrays.copyOfRange(m, 0, bestIndex);
         int nl = m[bestIndex];
         cl = findMinCutCost2(ml, nl);
      }
      if (bestIndex < m.length - 1) {
         int[] mr = Arrays.copyOfRange(m, bestIndex + 1, m.length);
         int nr = n - m[bestIndex];
         for (int j=0; j<mr.length; j++) {
         mr[j] = mr[j] - m[bestIndex];
      }
      cr = findMinCutCost2(mr, nr);
   }
   return n + cl + cr;
}

2. 恒定时间多切

无需计算最小成本，只需使用不同的索引和缓冲区。由于此方法在恒定时间内执行，因此它总是返回 n。另外，该方法实际上将字符串拆分为子字符串。

public int findMinCutCost3(int[] m, int n) {
   char[][] charArr = new char[m.length+1][];
   charArr[0] = new char[m[0]];
   for (int i=0, j=0, k=0; j<n; j++) {
      //charArr[i][k++] = string[j];   // string is the actual string to split
      if (i < m.length && j == m[i]) {
         if (++i >= m.length) {
            charArr[i] = new char[n - m[i-1]];
         } else {
            charArr[i] = new char[m[i] - m[i-1]];
         }
         k=0;
      }
   }
   return n;
}

注意：最后一个方法可以很容易地修改为接受String str参数而不是nset n = str.length()，并String[]从charArr[][].

于 2012-04-09T05:50:57.400 回答
3

对于动态规划，我声称你真正需要知道的是状态空间应该是什么——如何表示部分问题。

在这里，我们通过创建新的中断将一个字符串分成 m+1 个片段。我声称一个好的状态空间是一组 (a, b) 对，其中 a 是子串的开始位置，b 是同一子串的结束位置，计为最后的中断数分解的字符串。与每对相关的成本是分解它的最低成本。如果 b <= a + 1，则成本为 0，因为没有更多的中断可放入。如果 b 更大，则该子字符串中下一个中断的可能位置是点 a+1、a+2 ,... b-1。不管我们把它放在哪里，下一次休息都会花费 ba，但是如果我们把它放在位置 k，那么以后休息的最小成本是 (a, k) + (k, b)。

因此，要使用动态规划解决这个问题，请建立一个最小成本表 (a, b)，您可以在其中通过考虑 k - 1 个可能的中断然后查找字符串的成本来计算具有 k 部分的字符串的中断成本最多有 k - 1 个部分。

对此进行扩展的一种方法是首先创建一个表 T[a, b] 并将该表中的所有条目设置为无穷大。然后再次检查表，其中 b <= a+1 放置 T[a,b] = 0。这将填充表示原始字符串部分的条目，这些部分不需要进一步切割。现在扫描表格，对于每个 T[a,b] 且 b > a + 1 考虑所有可能的 k 使得 a < k < b 并且如果 min_k ((break between a and b) + T[a,k] + T[k,b]) < T[a,b] 将 T[a,b] 设置为该最小值。这表明您现在知道一种方法可以廉价地切分 T[a,k] 和 T[k,b] 表示的子字符串，因此这为您提供了一种更好的切分 T[a,b] 的方法。如果你现在重复这 m 次你就完成了 - 使用标准的动态编程回溯来制定解决方案。如果您为每个 T[a,

于 2012-04-09T11:58:27.183 回答
2

蟒蛇代码：

mincost(n, cut_list) =min {   n+ mincost(k,left_cut_list) + min(n-k, right_cut_list) }


import sys

def splitstr(n,cut_list):

        if len(cut_list) == 0: 
            return [0,[]]
        min_positions = []
        min_cost = sys.maxint
        for k in cut_list:
            left_split = [ x for x in cut_list if x < k]
            right_split = [ x-k for x in cut_list if x > k] 
            #print n,k, left_split, right_split
            lcost = splitstr(k,left_split)
            rcost = splitstr(n-k,right_split)      
            cost = n+lcost[0] + rcost[0]
            positions = [k] + lcost[1]+ [x+k for x in rcost[1]] 
            #print "cost:", cost, " min: ", positions
            if cost < min_cost:
                min_cost = cost
                min_positions = positions

        return ( min_cost, min_positions) 



print splitstr(20,[3,10,16])  # (40, [10, 3, 16])

print splitstr(20,[3,10]) # (30, [10, 3])

print splitstr(5,[1,2,3,4,5]) # (13, [2, 1, 3, 4, 5])

print splitstr(1,[1]) # (1, [1]) # m cuts m+1 substrings
于 2012-10-16T01:20:32.423 回答
0

这是一个 c++ 实现。它是使用 DP 的 O(n^3) 实现。假设切割数组是排序的。如果不是，则需要 O(n^3) 时间对其进行排序，因此渐近时间复杂度保持不变。

#include <iostream>
#include <string.h>
#include <stdio.h>
#include <limits.h>
using namespace std;
int main(){
    int i,j,gap,k,l,m,n;
    while(scanf("%d%d",&n,&k)!=EOF){

        int a[n+1][n+1];
        int cut[k];
        memset(a,0,sizeof(a));
        for(i=0;i<k;i++)
            cin >> cut[i];
        for(gap=1;gap<=n;gap++){
            for(i=0,j=i+gap;j<=n;j++,i++){
                if(gap==1)
                    a[i][j]=0;
                else{
                    int min = INT_MAX;
                    for(m=0;m<k;m++){
                        if(cut[m]<j and cut[m] >i){
                            int cost=(j-i)+a[i][cut[m]]+a[cut[m]][j];

                            if(cost<min)
                                min=cost;
                        }
                    }
                    if(min>=INT_MAX)
                    a[i][j]=0;
                    else
                        a[i][j]=min;
                }
            }
        }
        cout << a[0][n] << endl;
    }
    return 0;
}
于 2015-11-14T20:28:12.157 回答