动态规划——钢条切割java

【问题】：给定一段长度为n英寸的钢条和一个价格表pi（i = 1，2，3…n)求切割方案使得销售受益rn最大。

例如 n = 4
切割方案以及对应的收益为：

【用自顶向下的递归】

//CUT-ROD（p，n）
if  n == 0
     return 0
 q = -无穷
 for i = 1 to  n
     q = max(q,p[i]+CUT-ROD(p,n-i))
 return q;

【用动态规划的思想解决】
动态规划方法仔细安排就切顺序，对每个子问题只求解一次，并将结果保存下来，如果此后自此需要此问题的解，只需查找保存的结果，而 不必重新计算。

动态规划有两种等价的实现方法：
方法一：带备忘的自顶向下法
此方法按自然的递归形式编写过程，但过程会保存每个子问题的解（保存在数组或散列表中）。当需要一个子问题的解时，过程首先检查是否已经保存过此解，是，返回值。

MEMOIZED-CUT-ROD(p,n)
let r[0..n] be a new array
for i = 0 to n
    r[i] = -无穷
return MEMOIZED-CUT-ROD-AUX(p，n，r）

MEMOIZED-CUT-ROD-AUX(p，n，r）
if(r[n]>=0
    return r[n]
if n==0
   q = 0
else q= -wuqiong
   for i = 1 to n
        q = max(q,p[i] + MEMOIZED-CUT-ROD-AUX(p，n-i，r）
r[n] = q
return q

方法二：自底向上法
需要恰当的定义子问题的“规模”，使得任何问题的求解都只依赖于“更小的"子问题的求解。按由小到大的顺序进行求解。

//BOTTOM-UP-CUT-ROD(p,n)
let r[0,1,2...n] be a new array
r[0] = 0
for j = 1 to n
     q = -wuqiong
     for i = 1 to j
         q = max(q,p[i] + r[j-i]
     r[j] = q
return r[n]

扩展版本：不仅保存最优收益值，还保存对应的切割方案

//EXTENDED-BOTTOM-UP-CUT-ROD(p,n)
let r[0,1,2...n] and s[0...n0be a new array
r[0] = 0
for j = 1 to n
     q = -wuqiong
     for i = 1 to j
         if q<p[i]+r[j-i]
             q = p[i]+r[j-i]
             s[j] = i
         r[j] = q
return r and s

【java实现】

package 动态规划;

public class 钢筋分割 {
	//递归方法
	
    public static int cut_rod(int[] p,int n){
        if (n==0){
            return 0;
        }
        int q=-1;
        for (int i=1;i<=n;i++){
            q=Math.max(q,p[i]+cut_rod(p,n-i));
        }
        return q;
    }
    
    //带备忘的自顶向下
    public static int memoizedCutRod(int[] p,int n){
    	int[] r = new int[n+1];
    	for (int i = 0;i < r.length;i++){
    		r[i] = -1;
    	}
    	return MEMOIZED_cut_rod_aux(p,n,r);
    }
    
    public static int MEMOIZED_cut_rod_aux(int[] p,int n,int[]r){
    	if(r[n] >= 0){
    		return r[n];
    	}
    	int q = -1;
    	if(n == 0)  q = 0;
    	else{
    		for(int i = 1;i<=n;i++){
    			q = Math.max(q,p[i]+MEMOIZED_cut_rod_aux(p,n-i,r));
    		}
    	}
    	r[n] = q;
		return q;
    }
    
    //使用自底向上
    public static int bottomUpCutRod(int[] p,int n){
    	int[] r = new int[n+1];
    	for(int i = 0;i<r.length;i++){
    		r[i] = 0;
    	}
    	for(int j = 1;j <= n;j++){
    		int q = -1;
    		for(int i = 1;i<=j;i++){
    			q = Math.max(q, p[i] + r[j-i]);
    		}
    		r[j] = q;
    	}
    	return r[n];
    }
    
    public static void main(String[] args) {
		int[] p = {0,1,5,8,9,10,17,17,20,24,30};
		int n = 4;
		int resultDigui = cut_rod(p,n);
		System.out.println("使用递归方法求得最优收益为"+resultDigui);
		int resultBeiwang = memoizedCutRod(p,n);
		System.out.println("使用带备忘方法求得最优收益为"+resultBeiwang);
		int resultZidiXiangshang = bottomUpCutRod(p,n);
		System.out.println("使用自底向上方法求得最优收益为"+resultZidiXiangshang);
    }

}

运行结果：