本文最后更新于 677 天前,其中的信息可能已经有所发展或是发生改变。
问题描述
某公司购买长钢条,将其切割后进行出售。切割钢条的成本可以忽略不计,钢条的长度为英寸。已知价格表 p ,其中 π 表示长度为 i 英寸的钢条的价格。现要求解使销售收益最大的切割方案
问题分析
假设长钢条的长度为 n 英寸,最佳切割方案的最左边切割段长度为 i 英寸,则继续求解剩余长度为 m−1 英寸钢条的最佳切割方案。考虑所以可能的 i ,得到的最大收益 rn 对应的切割方案即为最佳切割方案。rn 的递归定义如下
rn=max1≤i≤n(pi+rn−i)
C 代码
对此问题有两种方案
(1) 分治 (自顶向下)
int Top_Down_Cut_Rod(int p[], int n){ int r=0; // 最大价值 int i; if(n==0){ retrun 0; } for(i=1; i<=n; i++){ int tmp = p[i]+Top_Down_Cut_Rod(p, n-i); r = (r>=tmp) ? r : tmp; } return r; }
时间复杂度 O(2n)
(2) 动态规划 (自底向上)
int Bottom_Up_Cut_Rod(int p[], int n, int *s){ // *s:子问题最优切割方法 int r[n+1]; // 子问题最优价值 r[0]=0; for(int j=1; j<=n; j++){ int tmp=0; for(int i=1; i<=j; i++){ if(p[i]+r[j-1] > tmp){ tmp = p[i]+r[j-i]; s[j]=i; } } r[i]=tmp; } return r[n]; }
时间复杂度 O(n2)
其他
在搜索过程中发现已有的文章:【基础算法】动态规划详解 —— 钢条切割