15.1 动态规划-钢条切割

package cn.com.liuxiaofei;
 
public class Chapter15_1 {
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		testCutRod(30);
 
	}
 
	public static void testCutRod(int n) {
		int[] p = new int[] { 0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30, 31, 35, 37, 40, 41, 42, 45, 49, 52, 55, 55, 56, 58, 59, 62, 62, 65, 68, 66, 64, 64, 62,
				64, 66, 68, 66, 61, 69, 70, 72 };
		if (n > p.length - 1) {
			System.out.println("The max value of n should be " + (p.length - 1));
			return;
		}
		System.out.println("Using cutRod");
		long time = System.currentTimeMillis();
		int income = cutRod(p, n);
		System.out.println("Max Income:" + income);
		System.out.println("Time elapse:" + (System.currentTimeMillis() - time));
 
		int[] r = new int[n + 1];
		System.out.println("\nUsing cutRodWithMemo");
		time = System.currentTimeMillis();
		income = cutRodWithMemo(p, n, r);
		System.out.println("Max Income:" + income);
		System.out.println("Time elapse:" + (System.currentTimeMillis() - time));
 
		System.out.println("\nUsing cutRodWithBottomUpMemo");
		time = System.currentTimeMillis();
		income = bottomUpCutRodWithMemo(p, n);
		System.out.println("Max Income:" + income);
		System.out.println("Time elapse:" + (System.currentTimeMillis() - time));
 
		System.out.println("\nUsing extendBottomUpCutRodWithMemo");
		time = System.currentTimeMillis();
		int[][] rands = extendBottomUpCutRodWithMemo(p, n);
		System.out.println("Time elapse:" + (System.currentTimeMillis() - time));
		System.out.print("i\t");
		for (int i = 1; i <= n; i++) {
			System.out.print(i + "\t");
		}
		System.out.println();
		System.out.print("s[i]\t");
		for (int i = 1; i <= n; i++) {
			System.out.print(rands[1][i] + "\t");
		}
		System.out.println();
		System.out.print("r[i]\t");
		for (int i = 1; i <= n; i++) {
			System.out.print(rands[0][i] + "\t");
		}
		System.out.println();
		System.out.print("Take n = 17 for example:\nThe solution should be:");
		int testN = 17;
		while (testN > 0) {
			int s = rands[1][testN];
			System.out.print(s + " ");
			testN -= s;
		}
		System.out.println();
 
	}
 
	/**
	 * @param p The price for each inch
	 * @param n The total length of the rod
	 * @return The max income
	 */
	public static int cutRod(int[] p, int n) {
		if (n == 0) {
			return 0;
		}
		int q = Integer.MIN_VALUE;
 
		for (int i = 1; i <= n; i++) {
			int income = p[i] + cutRod(p, n - i);
			if (q < income) {
				q = income;
			}
		}
		return q;
	}
 
	/**
	 * @param p The price for each inch
	 * @param n The total length of the rod
	 * @param r The income record array
	 * @return The max income
	 */
	public static int cutRodWithMemo(int[] p, int n, int[] r) {
		if (n == 0) {
			return 0;
		}
		if (r[n] > 0) {
			return r[n];
		}
		int q = Integer.MIN_VALUE;
 
		for (int i = 1; i <= n; i++) {
			int income = p[i] + cutRodWithMemo(p, n - i, r);
			if (q < income) {
				q = income;
			}
		}
		r[n] = q;
		return q;
	}
 
	/**
	 * @param p The price for each inch
	 * @param n The total length of the rod
	 * @return The max income
	 */
	public static int bottomUpCutRodWithMemo(int[] p, int n) {
		if (n == 0) {
			return 0;
		}
		int[] r = new int[n + 1];
		r[0] = 0;
		int q = Integer.MIN_VALUE;
 
		for (int j = 1; j <= n; j++) {
			for (int i = 1; i <= j; i++) {
				int income = p[i] + r[j - i];
				if (q < income) {
					q = income;
				}
			}
			r[j] = q;
		}
		return q;
	}
 
	/**
	 * @param p The price for each inch
	 * @param n The total length of the rod
	 * @return The max income
	 */
	public static int[][] extendBottomUpCutRodWithMemo(int[] p, int n) {
		int[] r = new int[n + 1];
		int[] s = new int[n + 1];
		if (n == 0) {
			return new int[][] { r, s };
		}
		r[0] = 0;
		int q = Integer.MIN_VALUE;
 
		for (int j = 1; j <= n; j++) {
			for (int i = 1; i <= j; i++) {
				int income = p[i] + r[j - i];
				if (q < income) {
					q = income;
					s[j] = i;
				}
			}
			r[j] = q;
		}
		return new int[][] { r, s };
	}
 
}
 
 
输出结果
Using cutRod
Max Income:90
Time elapse:4105
 
Using cutRodWithMemo
Max Income:90
Time elapse:0
 
Using cutRodWithBottomUpMemo
Max Income:90
Time elapse:0
 
Using extendBottomUpCutRodWithMemo
Time elapse:0
i	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	
s[i]	1	2	3	2	2	6	1	2	3	10	1	2	3	2	2	6	1	2	3	10	1	2	3	2	2	6	1	2	3	10	
r[i]	1	5	8	10	13	17	18	22	25	30	31	35	38	40	43	47	48	52	55	60	61	65	68	70	73	77	78	82	85	90	
Take n = 17 for example:
The solution should be:1 6 10