ダイナミックプランニングの最大積問題

3425 ワード

プログラミング安徽省にある地名。同前

動的計画問題を解く核心は、段階と段階の間の状態変化の法則を特定し、それによって状態転化の決定を制定し、前の段階のすべての局所最適状態値から次の段階の局所最適を押し出し、さらにグローバル最適を出すことにある.問題を解く際には,現在得られている局所最適値を保存するために通常2次元配列を構築し,次の段階の最適値を導く際に前の段階で得られた結果を用いて解くことができ,これは明らかに窮挙よりも効率的である.動的計画の1つの思想を覚えてください:多くの現在の局所最適は未来の最適が見えませんが、未来の最適は必ず現在の局所最適を含みます.
ある年の情報学コンテストを例にとると、長さNの数字文字列sにr個の乗算番号を挿入し、sをr+1部分に分割し、その最大積を求める.構想:このテーマは動的計画の思想で解くことができて、sの最大積は局部の最大積から得ることができるためです.この問題のフェーズを挿入乗数の個数として定義すると,フェーズ1は1番目の乗数を挿入し,フェーズ2は2番目の乗数を挿入し,...,フェーズrはr番目の乗数を挿入する.
各フェーズのステータスは、乗数を挿入する位置に対応します.また,各ステージの値セットは,そのステージの乗数によって決定される.例えば、ステージ1に対応する文字列の長さは明らかに1より大きく、ステージrに対応する文字列の長さはr+1より大きいべきである.
段階的な制定があり、さらにその状態転化の決定を分析した.
フェーズiの状態をf[i,k]とし,iは現在の数字文字列の末尾,すなわちs.sub(0,i),kは挿入されるk番目の乗数である.前述した将来の最適化は、現在の局所最適化を含むに違いない.ここでの未来はf[i,k].その最適値は、現在得られている最適解集合{f[j,k−1]}(k<=j解析により、状態遷移式は次のようになります.
f[i,k]=max{f[[j][k-1]*Int(s.substring(j,i)}そのうち(j>=k&&j状態遷移式があれば,プログラミングが容易になる.

Javaコード

import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class MaxMultiplication {
	
	/**
	 *      N       r   ，     r+1  ，      
	 * @param integerNum:        
	 * @param mSignNum：       
	 * @return     
	 */
	public static long handleMaximumMultiplicationWithMultipleSign(String integerNum, int mSignNum)
	{
		if(integerNum==null||mSignNum<0||mSignNum>=integerNum.length())
			throw new IllegalArgumentException("Wrong Arguments Input!");
	
		boolean result = isNaturalNumber(integerNum);
		
		if(!result)
			throw new IllegalArgumentException("Please input a natural number!");
		
		int numLength=integerNum.length();
		int[][] dpMultiTable=new int[numLength+1][mSignNum+1];//       
		
		for(int t=1;t<=numLength;t++)//          :    0     
		{
			dpMultiTable[t][0]=Integer.parseInt(integerNum.substring(0,t));
		}
		
		for(int r=1;r<=mSignNum;r++)//         （       ：x）
		{
			for(int i=r+1; i<=numLength;i++)//         （          ：y）
			{
				//    ( r-1       r      )，    f(i,r)       
				//j    r        
				int current_max=0;
				for(int j=r;j<i;j++)
				{
					int currentvalue=dpMultiTable[j][r-1]*Integer.parseInt(integerNum.substring(j,i));
					if(current_value>current_max)
					{
						dpMultiTable[i][r]=current_value;
						current_max=current_value;
					}
				}
			}
		}
		
		return dpMultiTable[numLength][mSignNum];	
	}


	/**
	 *           
	 * @param integerNum
	 * @return
	 */
	public static boolean isNaturalNumber(String integerNum) {
		String reg = "^[1-9](\\d*)$";
		Pattern p = Pattern.compile(reg);
		Matcher m = p.matcher(integerNum);
		boolean result = m.find();
		return result;
	}


	/**
	 * @param args
	 */
	public static void main(String[] args) {

        System.out.println(handleMaximumMultiplicationWithMultipleSign("12345",2));
        System.out.println(handleMaximumMultiplicationWithMultipleSign("10",0));
	}

}

D. Constructing the Array

JAva ioストリームクラスの機能概要