关于算法:算法DP之钢条切割问题

DP的四个步骤

  1. 刻画一个最优解的结构特征。
  2. 递归地定义最优解的值。
  3. 计算最优解的值,通常采纳自底向上法。
  4. 利用计算出的信息结构一个最优解。

前三步是DP求解的根底。若仅须要一个最优解的值,而非解自身,可疏忽第四步。若需第四步,有时需在执行第3步的过程中保护一些额定的信息,以便结构一个最优解。

钢条切割例子

场景:把长钢条切割为短钢条发售。切割工序自身无老本。求最佳切割计划。

假设:发售一段长度为 i 英寸的钢条的价格为Pi(i = 1, 2, …, )单位:$,钢条长度均为整英寸。下图为价格表。

问题形容:给定一段长度为n英寸的钢条和一个价格表,求切割计划,使销售收益Rn最大。注:若长度为n英寸的钢条的价格Pn足够大,最优解可能就是齐全不须要切割。

思考长度为4的状况,下图给出了4英寸钢条的所有切割计划。

切成两段各长2英寸的钢条,将产生P2 + P2 = 5 + 5 = 10 的收益,为最优解。

长度为n英寸的钢条共有2^(n-1)种不同切割计划,因为在间隔钢条左端 i (i=1, 2, … , n-1)英寸处,总是能够抉择切割或者不切割。用一般的加法符号示意切割计划,因而7=2+2+3示意将长度为7的钢条切割为3段:2英寸,2英寸,3英寸。

若一个最优解将钢条切割为k段(1≤k≤n),那么最优切割计划 n = i1 + i2 + … + ik.

将钢条切割为长度别离为i1, i2, … , ik的小段,失去的最大收益为 Rn = Pi1 + Pi2+…+Pik

对于下面表格的价格样例,能够察看所有最优收益值Ri (i: 1~10)以及最优计划:

长度为1:切割计划1=1(无切割)。最大收益R1 = 1

长度为2:切割计划2=2(收益5),1+1=2(收益2)。最大收益R2 = 5

长度为3:切割计划3=3(收益8),1+2=3(收益6),2+1=3(收益6)。最大收益8

长度为4:切割计划4=4(收益9),1+3=4(收益9),2+2=4(收益10),3+1=4(收益9),1+1+2=4(收益7),1+2+1=4(收益7),2+1+1=4(收益7),1+1+1+1=4(收益4)。最大收益10

长度为5:切割计划5=5(10),1+4=5(10),2+3=5(13),1+1+3=5(10),2+2+1=5(11),1+1+1+1+1=5(5),其余是后面的排列。最大收益13

顺次求出。。。

更个别的,对于Rn(n≥1),能够用更短的钢条的最优切割收益来形容它:

Rn = max(Pn, R1+Rn-1, R2 + Rn-2, … , Rn-1 + R1)

  • 第一个参数Pn对应不切割,间接发售长度为n的计划。
  • 其余n-1个参数对应n-1种计划。对每个i=1,2,….,n-1,将钢条切割为长度为i和n-i的两段,接着求解这两段的最优切割收益Ri和Rn-i;(每种计划的最优收益为两段的最优收益之和)。
  • 因为无奈预知哪种计划会取得最优收益,必须考查所有可能的 i ,选取其中收益最大者。若不切割时收益最大,当然抉择不切割。

留神到:

  • 为了求解规模为n的原问题,先求解子问题(子问题模式齐全一样,但规模更小)。
  • 即首次实现切割后,将两段钢条看成两个独立的钢条切割问题实例。
  • 通过组合两个相干子问题的最优解,并在所有可能的两段切割计划中获取收益最大者,形成原问题的最优解。

称钢条切割问题满足最优子结构性质:

问题的最优解由相干子问题的最优解组合而成,而这些子问题能够独立求解。

除上述解法,问题可化简为一种类似的递归:从右边切割下长度为 i 的一段,只对左边剩下的长度为 n-i 的一段进行持续切割(递归求解),对右边一段则不再进行切割。

即问题合成的形式为:将长度为n的钢条合成为右边开始一段,以及残余局部持续合成的后果。(这样,不做任何切割的计划能够形容为:第一段长度为n,收益为Pn,残余局部长度为0,对应收益为R0 = 0)。于是失去下面公式的简化版本:

在此公式中,原问题的最优解只蕴含一个相干子问题(右端残余局部的解),而不是两个。

自顶向下递归实现的伪代码:Cut-Rod(p, n)

Cut-Rod(p, n)
1    if n==0
2        return 0
3    q = -∞
4    for i = 1 to n
5        q = max(q, p[i] + Cut-Rod(p, n-i))
6    return q 

该过程以价格数组p[1…n]和整数n为输出,返回长度为n的钢条的最大收益。

若n=0,不可能有任何收益,所以第二行返回0.

第3即将最大收益初始化为负无穷,以便第4第5行的for循环能正确计算。

带备忘的自顶向下法(top-down with memorization)

  • 此办法依然依照天然的递归模式编写过程,然而过程会保留每个子问题的解(通常保留在一个数组或散列表中)。
  • 当须要一个子问题的解时,过程首先查看是否曾经保留过此解,

    • 如果是,则间接返回保留的值,从而节俭了计算工夫;
    • 否则,依照通常形式计算这个子问题。

JAVA实现:

public static void main(String[] args) {
  int[] p = new int[]{1, 5, 8, 9, 10};
  int result = memorizedCutRod(p, 5);
  System.out.println(result);
}
private static int memorizedCutRod(int[] p, int n) {
  int[] r = new int[n + 1];
  Arrays.fill(r, Integer.MIN_VALUE);
  return memorizedCutAux(p, n, r);
}
private static int memorizedCutAux(int[] p, int n, int[] r) {
  if (n == 0) {
    r[n] = 0;
  }
  if (r[n] >= 0) {
    return r[n];
  }
  int q = Integer.MIN_VALUE;
  for (int i = 1; i <= n; i++) {
    q = Math.max(q, p[i - 1] + memorizedCutAux(p, n - i, r));
  }
  r[n] = q;
  return q;
}

自底向上法(bottom-up method)

  • 该办法个别须要失当定义子问题“规模”的概念,使得任何子问题的求解都只依赖于“更小的”子问题的求解。
  • 因此能够将子问题按规模排序,按由小到大的程序进行求解。
  • 当求解某个子问题时,所依赖的那些更小的子问题都曾经求解结束,后果曾经保留。
  • 每个子问题只求解一次,当求解它时(也是第一次遇到它),所有前提子问题都曾经求解实现。

两种办法失去的算法具备雷同的渐进运行工夫,

  • 仅有的差别是在某些非凡状况下,自顶向下办法并未真正递归地考查所有可能的子问题。
  • 因为没有频繁的递归调用开销,自底向上的复杂度函数通常具备更小的系数。

JAVA实现:

public static void main(String[] args) {
  int[] p = new int[]{1, 5, 8, 9, 10};
  int result1 = bottomUpCutRod(p, 5);
  System.out.println(result1);
}
private static int bottomUpCutRod(int[] p, int n) {
  int[] r = new int[n + 1];
  r[0] = 0;
  for (int i = 1; i <= n; i++) {
    int q = Integer.MIN_VALUE;
    for (int j = 1; j <= i; j++) {
      q = Math.max(q, p[j - 1] + r[i - j]);
    }
    r[i] = q;
  }
  return r[n];
}

参考文章:https://segmentfault.com/a/11…
参考书目:算法导论

【腾讯云】轻量 2核2G4M,首年65元

阿里云限时活动-云数据库 RDS MySQL  1核2G配置 1.88/月 速抢

本文由乐趣区整理发布,转载请注明出处,谢谢。

您可能还喜欢...

发表回复

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

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据