动态规划之钢条切割问题 冷不防 2022-07-12 05:13 135阅读 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]; } }
还没有评论,来说两句吧...