7

特定の文字列処理言語は、文字列を 2 つに分割する基本的な操作を提供します。この操作には元の文字列のコピーが含まれるため、カットの場所に関係なく、長さ n の文字列に対して n 単位の時間がかかります。ここで、文字列を多くの断片に分割したいとします。休憩の順序は、総実行時間に影響を与える可能性があります。たとえば、位置 3 と 10 で 20 文字の文字列をカットしたい場合、位置 3 で最初のカットを行うと 20+17=37 の合計コストが発生しますが、位置 10 を最初に行うと 20+ のコストがかかります。 10=30。

長さ n の文字列の m 個の切断位置が与えられた場合に、文字列を m + 1 個に分割する最小コストを求める動的計画法のアルゴリズムを与えてください。

この問題は、「アルゴリズム」の第 6 章 6.9 からのものです。

この問題には答えがないので、こう考えました。

文字列の開始インデックス、終了インデックス、および使用できる残りのカット数についてOPT(i,j,n)、文字列を切断する最小コストとして定義します。ijn

ここに私が得るものがあります：

OPT(i,j,n) = min {OPT(i,k,w) + OPT(k+1,j,n-w) + j-i} for i<=k<j and 0<=w<=n

それは正しいですか？助けてください、thx!

4

2 に答える 2

3

あなたの再発の関係はもっと良くなると思います。これが私が思いついたものです。コスト（i、j）をインデックスiからjに文字列を切り取るコストに定義します。それで、

cost(i,j) = min {length of substring + cost(i,k) + cost(k,j) where i < k < j}
于 2015-11-12T23:22:05.513 に答える
0 
 void  s_cut()    
  {
    int l,p;
    int temp=0;
    //ArrayList<Integer> al = new ArrayList<Integer>();
    int al[];
    Scanner s=new Scanner(System.in);
    int table[][];
    ArrayList<Integer> values[][];
    int low=0,high=0;
    int min=0;

    l=s.nextInt();
    p=s.nextInt();

    System.out.println("The values are "+l+"  "+p);

    table= new int[l+1][l+1];
    values= new ArrayList[l+1][l+1];
    al= new int[p];

    for(int i=0;i<p;i++)
    {
        al[i]=s.nextInt();

    }

    for(int i=0;i<=l;i++)
    for(int j=0;j<=l;j++)
        values[i][j]=new ArrayList<Integer>();

    System.out.println();

    for(int i=1;i<=l;i++)
        table[i][i]=0;
    //Arrays.s
    Arrays.sort(al);

    for(int i=0;i<p;i++)
    {
        System.out.print(al[i]+ "  ");

    }


    for(int len=2;len<=l;len++)
    {
        //System.out.println("The length is  "+len);

        for(int i=1,j=i+len-1;j<=l;i++,j++)
        {

            high= min_index(al,j-1);
            low= max_index(al,i);

            System.out.println("Indices are "+low+"  "+high);

            if(low<=high && low!=-1 && high!=-1)
            {

            int cost=Integer.MAX_VALUE;;

            for(int k=low;k<=high;k++)
            {
                //if(al[k]!=j)
                temp=cost;
                cost=Math.min(cost, table[i][al[k]]+table[al[k]+1][j]);

                if(temp!=cost)
                {
                    min=k; 
                    //values[i][j].add(al[k]);
                    //values[i][j].addAll(values[i][al[k]]);
                    //values[i][j].addAll(values[al[k]+1][j]);
                    //values[i][j].addAll(values[i][al[k]]);
                }

                //else
                //cost=0;
            }

            table[i][j]= len+cost;

            values[i][j].add(al[min]);
            //values[i][j].addAll(values[i][al[min]]);
            values[i][j].addAll(values[al[min]+1][j]);
            values[i][j].addAll(values[i][al[min]]);

            }

            else
                table[i][j]=0;

            System.out.println(" values are "+i+"  "+j+"  "+table[i][j]);
        }
    }

    System.out.println(" The minimum cost is "+table[1][l]);

    //temp=values[1][l];
    for(int e: values[1][l])
    {
        System.out.print(e+"-->");

    }

}

上記のソリューションの複雑さは O(n^3) です。

于 2013-11-29T13:03:37.230 に答える