动态规划算法 ——钢条切割问题

动态规划算法

——钢条切割问题

（原创内容，转载请注明来源，谢谢）

一、问题

长度为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