动态规划之钢条切割问题

冷不防 2022-07-12 05:13 172阅读 0赞

**动态规划用于解决最优化问题，即有很多可行解，每个解都有一个值，希望找到最优值（最大值或最小值）得解。**

**解决的问题具有最优子结构性质：最优解由相关子问题的最优解组合而成，子问题可独立求解。**

**问题描述：给定钢条，总长度为n，价格随长度i为Pi,求最大收益Rn。**

**问题分析：长度为n的钢条有2的n-1次方种切割方案。**

**求解规模为n的原问题，县求解形式完全一样但规模更小的子问题。Rn=max（Pn,r1+rn-1,r2+rn-2.......rn-1+r1）**

**还有一种递归方法求解（即只看右边）：Rn=max（Pi+rn-i）(1<=i<=n),此时只包含一个相关子问题，是自顶向下的递归实现。但是效率差，n每增大1，运行时间会加一倍。**

**动态规划优化求解：有两种等价实现方法**

**带备忘录的自顶向下法**

#include <iostream>
    using namespace std;
    int main()
    {
    int  n;
    int P[100];
    int R[100];
    for(int i=1;i<101;i++)
    {
    	R[i]=-1;
    }
    }
    int cut_rod(int P[],int n,int R[])
    {
    	if(R[n]>=0) return R[n];
    	int r;
    	if(n==0) r=0;
    	else
    	{
    		r=-1;
    		for(int i=1;i<=n;i++)
    			r=max(r,P[i]+cut_rod(P,n-i,R));
    	}
    	R[n]=r;
    	return r;
    }

自底向上法

#include <iostream>
    using namespace std;
    int P[100];
    int R[100];
    int n;
    int bottom_up_cut_rod(int P[],int n,int R[])
    {
    	R[0]=0;
    	for(int j=1;j<=n;j++)
    	{
    		int r=-1;
    		for(int i=1;i<=j;i++)
    			r=max(r,P[i]+R[j-i]);
            R[j]=r;
    	}
    	return R[n];
    }

**上面所求的结果为最优解的收益值，求解本身（一个长度列表，包含切割方案）则需扩展动态规划算法。**

**以自底向上的方法为例**

#include <iostream>
    using namespace std;
    int P[100];
    int R[100];
    int S[100];
    int n;
    int bottom_up_cut_rod(int P[],int n,int R[])
    {
    	R[0]=0;
    	for(int j=1;j<=n;j++)
    	{
    		int r=-1;
    		for(int i=1;i<=j;i++)
    			if(r<P[i]+R[j-i]) 
    			{
    				r=P[i]+R[j-i];
    				S[j]=i;
    			}
    		R[j]=r;
    	}
    }
    void print_cut_rod_solution(int P[],int R[])
    {
    	bottom_up_cut_rod(P,n,R);
    	while(n>0)
    	{
    		printf("%d",S[n]);
    		n-=S[n];
    	}
    }