动态规划——钢条切割java

╰半橙微兮° 2022-02-23 02:52 266阅读 0赞

【问题】：给定一段长度为n英寸的钢条和一个价格表pi（i = 1，2，3…n)求切割方案使得销售受益rn最大。  
![在这里插入图片描述][20190406090447645.png]  
例如 n = 4  
切割方案以及对应的收益为：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70]  
【用自顶向下的递归】

//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);
        }
    
    }

运行结果：  
![在这里插入图片描述][20190406101451720.png]

[20190406090447645.png]: /images/20220223/5810a3245fa74b04b2249ee2810d2ce9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70]: /images/20220223/ce109889f1784efaab32dba376da1445.png
[20190406101451720.png]: /images/20220223/d2420577988e40ec971e0186ad6b2b93.png