Processing math: 100%
算法 钢条切割问题
本文最后更新于 677 天前,其中的信息可能已经有所发展或是发生改变。

问题描述

某公司购买长钢条,将其切割后进行出售。切割钢条的成本可以忽略不计,钢条的长度为英寸。已知价格表 p ,其中 π 表示长度为 i 英寸的钢条的价格。现要求解使销售收益最大的切割方案

问题分析

假设长钢条的长度为 n 英寸,最佳切割方案的最左边切割段长度为 i 英寸,则继续求解剩余长度为 m1 英寸钢条的最佳切割方案。考虑所以可能的 i ,得到的最大收益 rn 对应的切割方案即为最佳切割方案。rn 的递归定义如下
rn=max1in(pi+rni)

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)

其他

在搜索过程中发现已有的文章:【基础算法】动态规划详解 —— 钢条切割

本文链接:算法 钢条切割问题
本文章由 yexca 采用 知识共享署名 - 非商业性使用 - 相同方式共享 4.0 国际许可协议 进行许可,转载请注明出处。
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇