某公司购买长钢条，将其切割后进行出售。切割钢条的成本可以忽略不计，钢条的长度为整英寸。已知价格表p，其中pi（i＝1，2，…，m）表示长度为i英寸的钢条的价格。现要求解使销售收益最大的切割方案。
求解此切割方案的算法基本思想如下：
假设长钢条的长度为n英寸，最佳切割方案的最左边切割段长度为i英寸，则继续求解剩余长度为n－i英寸钢条的最佳切割方案。考虑所有可能的i，得到的最大收益rn对应的切割方案即为最佳切割方案。rn的递归定义如下：
rn=max1≤i≤n(pi+rn-i)
对此递归式，给出自顶向下和自底向上两种实现方式。
【C代码】
/*常量和变量说明
n：长钢条的长度
p[]：价格数组
*/
#define LEN 100
int Top_Down_Cut_Rod(int p[],int n){/*自顶向下*/
int r=0;
int i;
if(n==0){
return 0;
}
for(i=1;（1）;i++){
int tmp=p[i]+Top_Down_Cut_Rod(p,n-i);
r=(r>=tmp）r：tmp;
}
return r;
}
int Bottom_Up_Cut_Rod(int p[],int n){/*自底向上*/
int r[LEN]={0};
int temp=0;
int i,j;
for(j=1;j＜=n;j++){
temp=0;
for(i=1;（2）;i++){
temp=（3）;
}
（4）;
}
return r[n];
}
【问题1】（8分）
根据说明，填充C代码中的空（1）～（4）。
【问题2】（7分）
根据说明和C代码，算法采用的设计策略为（5）。
求解rn时，自顶向下方法的时间复杂度为（6）；自底向上方法的时间复杂度为（7）（用O表示）。
正确答案及解析
正确答案
解析
【问题1】
（1）：i＜=n
（2）：i＜=j
（3）：(temp>=p[i]+r[j-i])?temp:(p[i]+r[j-i])
（4）：r[j]=temp
或
（3）：(temp>=r[i]+r[j-i])?temp:(r[i]+r[j-i])
（4）：r[j]=(temp>p[j])?temp:p[j];
【问题2】
（5）动态规划法
（6）O(2n)
（7）O(n2)
【问题1】
在自顶向下实现过程中，n-i表示规模从大到小即n-1~0，即对应i的初始值为1，结束值为n，第一空填写i＜=n，递归式也有范围提示可以参照。
在自底向上实现过程中，采用双重嵌套循环，内层循环从1~j，第二空填写i＜=j。
第三空和第四空比较复杂，是具体的实现过程，是本题的难点。
根据题干内容，本题考查的是钢条切割问题最优化问题，求解的思路即先考虑最左侧的切割考虑，再依次向右扩展，中间的最优解结果记录在数组r[]中，并用temp中间变量传递最大值。
根据递归式rn=max1≤i≤n(pi+rn-i)，即r[]最终结果是该过程的最大值，（3）空给temp赋值，那么（4）空应该是将这个中间值传给最终的rn，也就是代码中的r[j]，即第四空填写r[j]=temp，那么此时第三空对应最大值的求取，也就是本算法的核心，这里的最大值是在1~j的规模范围循环比较，用temp放置本轮结果，再与下一轮结果进行比较，第三空temp=(temp>=p[i]+r[j-i])?(temp:(p[i]+r[j-i])。
【问题2】
题干中提到说考虑所有可能的i，得到最大收益的方式，而自底向上算法实现时，使用到数组把其中最优的解记录，并用r[]记录中间解，因此本题算法策略是动态规划法。
动态规划法自顶向下时需要对规模n进行求取，此时需要递归至规模1并最终返回结果规模n的解并记录，规模n-1同样如此，时间复杂度较大，可以达到O(2n)；
动态规划法自底向上时先求取规模1的解并记录，然后查询规模1的解从而求解规模2的解，以此类推，直至求取至规模n，有查询和循环求解2层嵌套循环，时间复杂度为O(n2)。
包含此试题的试卷
你可能感兴趣的试题
-
- A.V(S2)和P(S4)
- B.P(S2)和V(S4)
- C.P(S2)和P(S4)
- D.V(S2)和V(S4)
- 查看答案
-
- A.V（S1）P（S2）和V（S3）
- B.P（S1）V（S2）和V（S3）
- C.V（S1）V（S2）和V（S3）
- D.P（S1）P（S2）和V（S3）
- 查看答案
-
- A.P（S4）和V（S4）V（S5）
- B.V（S5）和P（S4）P（S5）
- C.V（S3）和V（S4）V（S5）
- D.P（S3）和P（S4）V（P5）
- 查看答案
-
- A.P(S3)和V(S4)V(S5)
- B.V(S3)和P(S4)P(S5)
- C.P(S3)和P(S4)P(S5)
- D.V(S3)和V(S4)V(S5)
- 查看答案
-
- A.P（S2）和P（S4）
- B.P（S2）和V（S4）
- C.V（S2）和P（S4）
- D.V（S2）和V（S4）
- 查看答案