最大K乘积

最大K乘积的问题：

在一个长度为N的数字串中插入K-1个乘号,将N分成K部分，找出一种分法，使得这K个部分的最大乘积最大。

例如有一个数字串：312，当N=3，K=2时会有以下几种分法：

3*12=36   31*2=62

但是符合题目的是31*2=62，通过这个例子很明显的可以看出最大k乘积的问题，就是求一个数，将其分成k段，求出段相乘的最大值问题。

 

要求解此问题要用到动态规划的思想，在这里要用到两个数据来分别表示不同的含义

w(h1,h2)表示第h1位到第h2位所组成的十进制数（h2.>h1)

m(i,j)表示：前i位（从1.......N）分成j段所得的最大乘积，则可得到如下的DP方程

if(j==1)   m(i,1)=w(1,i);

if(j>=1&&j<k)

  m(i,j)=max{ m(d,j-1)*w(d+1,i)(1<d<i) }

else if(i<j)   m(i,j)=0;

 

这是一个动态规划的式子。

 

这里是java实现的主要代码：

/**
	 * 对得到的数组进行处理，得到最大K乘积
	 */
	private void maxValue() {

		int size = num.length;
		
		/**
		 *  先把value[i][j]初始化，其代表的是从i开始到j所代表的的整数i<j
		 */
		for (int i = 0; i < size; i++) {
			value[i][i] = num[i];
			for (int j = i + 1; j < size; j++) {
				value[i][j] = value[i][j - 1] * 10 + num[j];
			}
		}

		
		/**
		 * 初始化maxValue第一列,即前i+1位，分成1段所得的最大乘积
		 * 初始化bit第一行和第一列，即当前i+1位分成1段时最后一个乘号的位置，和第一位分成i+1段时最后一个乘号出现的位置，都将他们的初始化为零
		 */
		for (int i = 0; i < size; i++) {
			maxValue[i][0] = value[0][i];
			bit[0][i] = 0;
			bit[i][0] = 0;
		}

		// 关键代码得maxValue[i][j]的值，即前i+1位分成j+1段时的最大乘积（因为下表从零开始）
		for (int i = 1; i < size; i++) {
			//分成二段到intDuan段
			for (int j = 1; j < intDuan; j++) {
				int max = 0;
				int index = 0;
				/**
				 * 找出从前1位到前i-1位分成j-1段时的值与后面的值相乘得到的最大值
				 * 公式：m(i,j)=max{m(d,j-1)*w(d+1,i)}  (1<d<i)
				 */
				for (int k = 0; k < i; k++) {
					if (maxValue[k][j - 1] * value[k + 1][i] > max) {
						max = maxValue[k][j - 1] * value[k + 1][i];
						index = k + 1;
					}
				}
				//得到最大的乘积时，最后一个乘号的位置
				bit[i][j] = index;
				maxValue[i][j] = max;
			}
		}
}

 

 

 

 

全部的代码：

 

package 动态规划;

import javax.swing.JOptionPane;

/**
 * 求最大K乘积
 * 
 * @author ZDX
 * 
 */
public class MaxK {

	int[] num;
	int[][] value;
	// 用来记录最大k乘积
	int[][] maxValue;
	// 用来存储用户输入的分成的分数
	int intDuan;
	// 用来记录乘号最后出现的位置
	int[][] bit;

	int result;

	public MaxK() {
		// 得到要处理的字符串
		String strNum = "";
		while (strNum == null || strNum.equals("")) {
			strNum = JOptionPane.showInputDialog(null, "请输入要进行分解的整数");

		}
		// 将字符串转化为字节数组
		byte[] bt = strNum.getBytes();
		// 初始化
		num = new int[bt.length];
		value = new int[bt.length][bt.length];
		maxValue = new int[bt.length][bt.length];
		bit = new int[bt.length][bt.length];
		// 将得到的字节数组转化为整数数组
		for (int i = 0; i < bt.length; i++) {
			num[i] = bt[i] - 48;
		}

		strNum = "";
		while (strNum == null || strNum.equals("")) {
			strNum = JOptionPane.showInputDialog(null, "请输入要分成的段数：");
		}

		intDuan = Integer.parseInt(strNum);
		maxValue();
	}

	/**
	 * 对得到的数组进行处理，得到最大K乘积
	 */
	private void maxValue() {

		int size = num.length;
		
		/**
		 *  先把value[i][j]初始化，其代表的是从i开始到j所代表的的整数i<j
		 */
		for (int i = 0; i < size; i++) {
			value[i][i] = num[i];
			for (int j = i + 1; j < size; j++) {
				value[i][j] = value[i][j - 1] * 10 + num[j];
			}
		}

		
		/**
		 * 初始化maxValue第一列,即前i+1位，分成1段所得的最大乘积
		 * 初始化bit第一行和第一列，即当前i+1位分成1段时最后一个乘号的位置，和第一位分成i+1段时最后一个乘号出现的位置，都将他们的初始化为零
		 */
		for (int i = 0; i < size; i++) {
			maxValue[i][0] = value[0][i];
			bit[0][i] = 0;
			bit[i][0] = 0;
		}

		// 关键代码得maxValue[i][j]的值，即前i+1位分成j+1段时的最大乘积（因为下表从零开始）
		for (int i = 1; i < size; i++) {
			//分成二段到intDuan段
			for (int j = 1; j < intDuan; j++) {
				int max = 0;
				int index = 0;
				/**
				 * 找出从前1位到前i-1位分成j-1段时的值与后面的值相乘得到的最大值
				 * 公式：m(i,j)=max{m(d,j-1)*w(d+1,i)}  (1<d<i)
				 */
				for (int k = 0; k < i; k++) {
					if (maxValue[k][j - 1] * value[k + 1][i] > max) {
						max = maxValue[k][j - 1] * value[k + 1][i];
						index = k + 1;
					}
				}
				//得到最大的乘积时，最后一个乘号的位置
				bit[i][j] = index;
				maxValue[i][j] = max;
			}
		}

		
        /**
         * 输出将前i位分成j段时所得到的最大值maxValue[i][j]一一输出
         * result最终得到的是该数分成intDuan段相乘的最大值
         */	
		for (int i = 0; i < size; i++) {
			for (int j = 0; j < intDuan; j++) {
				System.out.print(maxValue[i][j] + "   ");
				result = maxValue[i][j];
			}
			System.out.println();
		}

		/**
		 * 输出将前i位分成j段相乘的最大值时最后一个乘号的位置
		 */
		for (int i = 0; i < size; i++) {
			for (int j = 0; j < intDuan; j++) {
				System.out.print(bit[i][j] + "   ");
			}
			System.out.println();
		}

		/**
		 * 得到最终的相乘形式，例:23*41
		 */
		String strOutput = "";
		int i = size - 1;
		int j = intDuan - 1;
		while (j > 0) {
			System.out.println(bit[i][j]);
			
			strOutput = "*" + value[bit[i][j]][i] + strOutput;
			/**
			 * value[bit[i][j]][i]表示的是从最后一个乘号到最后一位的值。这是一个迭代的过程，
			 * 当下一次时原本的数据会将value[bit[i][j]][i]从启辰上去除，再进行处理
			 * 例：数据2341，分成三（j=2，j从0开始计数）段，则最大相乘形式为2*3*41，最后一位的下表（从零开始）i=3后一个乘号出现的位置是bit[i][j]=2，则value[bit[i][j]][i]=41，
			 * 则下次对其进行处理的时候是23,剩下的是将其分成两段（j=1)，则i=1,即i=bit[i][j]-1;
			 */

			i = bit[i][j] - 1;
			
			j--;
		}
		//将最前面的一个数字加到字符串上
		strOutput = value[0][i] + strOutput;
		
		JOptionPane.showMessageDialog(null, "最大" + intDuan + "乘积为:" + result
				+ "\n相乘格式为： " + strOutput, "结果", 1);

	}


	public static void main(String[] args) {
		new MaxK();
	}
}

 测试如下：