动态规划算法 ——钢条切割问题
动态规划算法
——钢条切割问题
（原创内容，转载请注明来源，谢谢）
一、问题
长度为n米的钢条，需要切割成x断来贩卖。假设没有切割成本，且每种长度能够销售的价格是一个确定的值（例如长度1米可以卖1元，长度2米可以卖5元，长度3米可以卖6元等）。
现在假定已知每种长度可以销售的价格，求长度为n米的钢条切割后，可以销售得到的最大利润。
二、分析
对于任意长度为i米的钢条，要获得最大价值，要么不需要切割整个i来售卖，要么从左开始切割i’米（这一段不再切割），使得i’米的价格加上剩余i-i’米切割后的价格的总和最大。
三、解法一
根据分析可知，可以遍历不同的长度，并且取得最终的最大值。
代码如下：
public function solvingSlowDynamic($prices, $length)
{
$pricesCount = count($prices);
//待售长度为0的钢条，或价格表只有长度为0的价格，
if(empty($length) || 1 >= $pricesCount)
{
return 0;
}
$salePrice = 0;
//从切割长度为1开始，逐个计算价格
for($i = 1;$i < $pricesCount-1; $i++)
{
$salePrice = max($salePrice, $prices[$i] + $this->solvingSlowDynamic($prices, $length-$i));
}
return $salePrice;
}
四、解法二
解法一有个问题，当钢条长度太长时，计算会很慢。因为会重复计算许多中间节点的长度最佳售价。例如长度为10的钢条，从左切可以是0-10、1-9、2-8、3-7...，要计算9的售价则又需要计算0-9、1-8、2-7、3-6...，可以看到长度为2、3等的钢条，其价格需要重复计算。
易知，长度为n的钢条，有2^n种切割方案，故需要计算2^n次长度的售价。
为了加快速度，可以把中间结果缓存。
代码如下：
private $lengthPrices = array();//用于缓存中间计算结果
public function solvingFastDynamic($prices, $length)
{
//如果已经有缓存的结果则直接返回
if(isset($this->lengthPrices[$length]))
{
return $this->lengthPrices[$length];
}
$pricesCount = count($prices);
if(empty($length) || 1 >= $pricesCount)
{
return 0;
}
$salePrice = 0;
for($i = 1;$i < $pricesCount-1; $i++)
{
$salePrice = max($salePrice, $prices[$i] + $this->solvingSlowDynamic($prices, $length-$i));
}
//缓存计算结果
$this->lengthPrices[$length] = $salePrice;
return $salePrice;
}
五、解法三
除了缓存中间结果，还可以采用自底向上的方式计算，即先计算长度为0、1、2、3...的，则在计算长度为n的钢条时，可以直接利用前面的计算结果进行计算。
代码如下：
public function solvingNewDynamic($prices, $length)
{
//自底向上，计算出每个长度的最佳售价
$lengthPrices = array(0 => 0);
//记录每种长度下的最左端切割长度
$cutLength = array(0 => 0);
$pricesCount = count($prices);
for($i = 1;$i < $pricesCount-1; $i++)
{
$salePrice = 0;
for($j = 1; $j <= $i; $j++)
{
$tmpSum = $prices[$j] + $lengthPrices[$i-$j];
if($salePrice < $tmpSum)
{
$salePrice = $tmpSum;
//记录长度为i的钢条的最佳第一段切割长度
$cutLength[$i] = $j;
}
}
//记录长度为i的最佳售价
$lengthPrices[$i] = $salePrice;
}
return array($lengthPrices, $cutLength);
}
上面的解法中，除了计算出每个长度的最佳售价，还计算出每个长度的最左端的切割方案。实际中，如果需要长度为n的切割方案，则根据数组可以查出第一段的切割长度，假设为i，则此时再查表，找到长度为i的钢条的第一段切割方案。以此类推，推算出最终的切割方案。
——written by linhxx 2018.05.13