一个动态规划问题–钢条切割

一根钢条,1米的卖1元,2米的卖5元,3米的卖8元,问:一根10米的钢条,怎么切割才能获得最大利益?

怎么样,这个问题的简化版,你是不是很快就知道答案了呢?

简单的想法,我们是不是只需要算出每种方案每米钢条的单价就可以了呢?

比如,单价排序为:1/1 < 5/2 < 8/3

所以,我们切割的时候,应该优先选择3米的钢条,如果不够3米,那么优先选择2米的钢条,直到剩下1米为止。

最终,我们的方案如下:10=3+3+3+1,最大收益为25。是不是真的这么简单呢?

如果将这个问题推广一下,比如,我们的价格表很长,且钢条也不止10米,可能是100米,我们该怎么办呢?

下面就来介绍一下《算法导论》书中用到的动态规划算法求解这个问题。

变量的假设

假设价格表为p,p为一个数组,从0开始,那么上面这个简化版的价格表表示如下:

// 0米的钢条价格为0,符合逻辑
p = [0,1,5,8]

假设钢条长度为n,有:

n = 10

上面例子中我们的求解思路实际是错误的,只是例子中恰好等于最大值而已。上面思路其实是用到了贪心算法,优先取最优解,对于这个算法,有机会再讲解。

这里举一个反例来证明其错误,比如:

p = [0,1,5,8];

n = 4;

// 按文章开头的思路
// 4 = 3 + 1 收益为9
// 而 4 = 2 +2 收益为10

书中总共使用了三种方法来求解这个问题,这三种方法其实是同一种思路。

求解思路

上面的示例非常的简单,也没有用到书中的解答思路。书中的思路如下:

假设有个函数F(p,n)表示n米钢条对应价格表p的最大收益,那么F(p,n-i) 就表示n-i米钢条对应价格表p的最大收益,其中0<i<n。

对于n米的钢条,这个i值最多有n-1个,而这个i就表示我们的切割点。

所以,我们只需要比较 p[1] + F(p,n-1), p[2] + F(p,n-2),… ,  p[n-1] + F(p,1),p[n] + F(p,0)选取其中一个最大值即为我们的最大收益。

实质是将问题分解为这n个子问题p[1] + F(p,n-1), p[2] + F(p,n-2),… ,  p[n-1] + F(p,1),p[n] + F(p,0),只要求出这些子问题的最优解,那么我们的问题就得以解决。

三种方法的伪代码

法一:自顶向下递归

CUT-ROD(p,n)
   if n==0
      return 0
   q = -Infinity
   for i=1 to n
      q = max(q,p[i]+CUT-ROD(p,n-j))
   return q

这个方法,递归调用自身,计算每一个子问题的最大值,然后通过max函数取每一次比较的最大值保存在q中。

可以看出,这种方法的效率是最低的,因为子问题重复的概率非常大。下面两种方法是对这个方法的改进。

法二:带备忘的自顶向下递归

MEMOIZED-CUT-ROD(p,n)
   let r[0...n] be a new array
   for i=0 to n
      r[i]=-Infinity
   return MEMOIZED-CUT-ROD-AXU(p,n,r)


MEMOIZED-CUT-ROD-AXU(p,n,r)
   if r[n]>=0
      return r[n]
   if n==0
      q=0
   else
      q=-Infinity
      for i=0 to n
         q=max(q,p[i]+MEMOIZED-CUT-ROD-AXU(p,n-i,r))
   r[n]=q
   return q

这个方法使用中间过程MEMOIZED-CUT-ROD-AXU,其中通过r来保存每一个子问题最优解。

在中间过程开始时,如果r[n]>=0就表示这个子问题已经有了结果,直接就返回了,不会再次计算,所以效率会大大提高。

法三:自底向上法

BOTTOM-UP-CUT-ROD(p,n)
   let r[0...n] be a new array
   r[0]=0
   for j=1 to n
      q=-Infinity
      for i=1 to j
         q=max(q,p[i]+r[j-i])
      r[j]=q
   return r[n]

这个方法是对方法二的改进,只是将递归改成了迭代,这个方法的效率又会比方法二高一些,因为省略了递归调用的开销,但并不明显。

如果钢条的长度超过20米,方法一的计算时间会远远低于后面两个方法。

JavaScript代码实现

下面是我根据这个思路写的JavaScript代码

// 方法一:直接递归
function cut_rod(p,n){
   if(n===0)
      return 0;
   var q = 0;
   for(var i=1;i<=n;i++){
      var subMax = cut_rod(p,n-i,s)+p[i];
      q = q>=subMax?q:subMax;
   }
   return q;
}

// 方法二:带备忘的自顶向下
function memoized_cut_rod(p,n){
    return memoized_cut_rod_axu(p,n,{});
}

/**
 * 必须满足条件 n<=p.length-1
 */
function memoized_cut_rod_axu(p,n,r){
   if(parseInt(r[n])>0)
      return r[n];
   var q = 0;
   if(n===0)
      q=0;
   else{
      for(var i=1;i<=n;i++){
         var subMax = memoized_cut_rod_axu(p,n-i,r)+p[i];
         q = q>subMax?q:subMax;
      }
   }
   r[n]=q;
   return q;
}


// 方法三:自底向上法
function bottom_up_cut_rod(p,n) {
   var r=[];
   r[0]=0;
   for (var j=1;j<=n;j++){
      var q=0;
      for (var i=1;i<=j;i++)
         if(q<p[i]+r[j-i]){
            s[j]=i;
            q=p[i]+r[j-i];
         }
      r[j]=q;
   }
   return r[n];
}

然后,我们写一个测试程序来测试一下这三种方法。如下:

// 价格对照表
var p = [0,1,5,8,9,10,17,17,20,21,22,24,25,28,30,40,42,44,47,50,54,59,62,66,68];
// 钢条长度
var n = 24;

console.time('cut_rod');
console.log(cut_rod(p,n));
console.timeEnd('cut_rod');

console.time('memoized_cut_rod');
console.log(memoized_cut_rod(p,n));
console.timeEnd('memoized_cut_rod');


console.time('bottom_up_cut_rod');
console.log(bottom_up_cut_rod(p,n));
console.timeEnd('bottom_up_cut_rod');

测试输出如下(不同设备CPU不同,时间会有差别):

70
cut_rod: 295.94287109375ms
70
memoized_cut_rod: 0.340087890625ms
70
bottom_up_cut_rod: 0.1708984375ms

可以看出,同样是计算24米的钢条,方法一的时间是295ms,而后面两种方法的时间都在1ms内,相差几百倍!所以,一个好的算法是可以大大缩短计算时间的。

什么是动态规划?

看了上面的解答题,或许你会纳闷了,什么是动态规划呢?这个和动态规划有什么关系呢?

好吧,现在我们就给出动态规划的定义。

如果某个问题,可以通过分解原问题为不同的子问题,这些子问题和原问题具有相同的计算步骤,并且子问题或者子问题下的子子问题存在计算重叠的情况,我们就称这个问题为动态规划问题。

这个定义一给出,我相信聪明的你已经知道了。

我们的算法一并没有使用动态规划来求解问题。

因为虽然它分解了子问题,但是对于计算存在重叠的情况,算法并没有做处理,这种策略被称为分治算法。即,简单的分解,直接计算,不做处理。

而,算法二和算法三将所有子问题的解都保存了下来,在重叠的时候,直接查找这个保存的值,所以速度会快很多。

动态规划实质是一个算法特性,对于同一个问题,你可以使用动态规划算法,也可以使用其他算法。

总结

算法还有很多,慢慢学习。

还没有关注订阅号的朋友,扫描二维码,或者识别图片二维码关注哦。

有最新干货会第一时间通知您哦。

image.png



打赏作者

发表评论

电子邮件地址不会被公开。 必填项已用*标注