一道经典的动态规划问题题解

一道经典的动态规划问题题解

 

有一个由数字1，2，...，9组成的数字串（长度不超过200），问如何将M(M<=20)个加号("+")插入到这个数字串中，使所形成的算术表达式的值最小。请编一个程序解决这个问题。

注意：
加号不能加在数字串的最前面或最末尾，也不应有两个或两个以上的加号相邻。
M保证小于数字串的长度。

例如：数字串79846，若需要加入两个加号，则最佳方案为79+8+46，算术表达式的值133。

[输入格式］

从键盘读入输入文件名。数字串在输入文件的第一行行首（数字串中间无空格且不折行），Ｍ的值在输入文件的第二行行首。

[输出格式］

在屏幕上输出所求得的最小和的精确值。

[输入输出举例］

EXAM4.SAM
82363983742
3

输 入 输 出

EXAM4.SAM 2170

 

 

   易知，若用蛮力法进行求解，够呛了。明显，这是道经典的动态规划问题：

规划方程:

getResult[start,end]=min{getResult[start,index]+Num[index,end]} (start<index<=end-1)

边界值: getResult[0,end]= NUM[1,end] ;

其中：getResult[start,end]表示数字串第start到end位最小和

      Num[index,end]表示数字串从第index到end位所组成的数

注意到上式中，index取值范围极广。然而我们对该题细细分析时，发现当最小和时，组成该最小和的任意两个加法因子的长度不大于1；

故每个加法因子长度只的可能为m/(n+1)或m/(n+1)+1（这里m表示数字串的长度，n表示加法号个数），当（n+1）|m时，每个数字串长度便确定了，可直接求出。有了此约束条件，该算法的复杂度便下降了。其java实现程序如下：

 

import javax.swing.*;

import java.math.*;

public class Adders {

   

    private String numExp;      //定义数字串

    private int addNum;          //定义加法号个数

    private  int lengthPerNum;  //定义每个加法因子的最小长度

   

    public Adders(){

       //输入数字串和加法号个数，并求得LengthPerNum

       numExp = JOptionPane.showInputDialog(null,"Please input the expression of numbers:");

       addNum = Integer.parseInt(JOptionPane.showInputDialog(null,"the number of adding :"));

       lengthPerNum = numExp.length() / (addNum + 1);

    }

    //将数字串strNum转为数字

    private BigInteger num(String strNum){

       if(strNum.equals("")) return new BigInteger("9999999999");

       return new BigInteger(strNum);

      

    }

    //动态求得结果

    public BigInteger getResultByDp(int index,int num){

 

       if(num == 0)

           return num(numExp.substring(0, index));

       else{

           BigInteger result1;

           BigInteger result2;

           if(index<=lengthPerNum+1 )

              return new BigInteger("999999999");

           result1 = getResultByDp(index - lengthPerNum,num - 1).add(num(numExp.substring(index - lengthPerNum, index))) ;

           result2 = getResultByDp(index - lengthPerNum - 1,num - 1).add(num(numExp.substring(index - lengthPerNum - 1, index))) ;

           if(result1.compareTo(result2)>= 0)

              return result2;

           else

              return result1;

             

       }

    }

    //直接求得结果

    public BigInteger getResultByDiret(){

       BigInteger result = new BigInteger("0") ;

       for(int i=0;i <= addNum;i++)

           result = result.add(num(numExp.substring(i*lengthPerNum,(i+1)*lengthPerNum)));

       return result;

    }

   

    public static  void main(String args[]){

       Adders a = new Adders();

       if(a.numExp.length() == (a.addNum+1)*a.lengthPerNum)

           System.out.println("Result:"+a.getResultByDiret());

       else

           System.out.println("Result:"+a.getResultByDp(a.numExp.length(), a.addNum));

          

    }

}

 

说明：1）这里仅仅实现了求最小和功能，并未严格遵循输入输出规则。

为了防止溢出，使用了高精度数BigInteger。

      2）当然，由于长度为m/(n+1)和m/(n+1)+1的加法因子个数是确定的，也可以据此用枚举法实现，这里不再赘述。

      3）水平有限，欢迎大牛提出宝贵意见。