这篇本文主要介绍了动态规划问题的解决方法。动态规划的核心思想是将大问题拆解为小问题，并找到问题的最优子结构，然后构建子问题之间的状态转移函数。求解状态转移函数的一般思路如下：

1. 首先确定大问题，记为OPT(n)（其中n为问题的规模）

2. 然后找到次大问题，并假设次大问题的解已知。也就是说，在求解OPT(n)时，我们假设OPT(1)、OPT(2)、……、OPT(n-2)和OPT(n-1)都是已知的。尽管在某些情况下只需要用到OPT(n-1)来求解状态转移函数，但有些问题可能需要用到OPT(n-2)或OPT(n-k)。少数问题需要用到OPT(1)到OPT(n-1)的全部。

3. 通过观察和分析，得到大问题OPT(n)和次大问题OPT(n-1)之间的关系式

4. 将关系式中的n替换为i，得到一般的状态转移函数

5. 注意处理某些边界情况

带权区间调度问题是一个经典的可以用动态规划求解的问题。它的定义如下：

接下来，我们按照上述思路来解决这个问题：

首先定义大问题。我们可以将工作(1, 2, ..., n)的最大权重记为OPT(n)。

那么次大问题就是工作(1)、(1, 2)、……、(1, 2, ..., n-1)等的最大权重，分别记为OPT(1)、OPT(2)、……、OPT(n-2)、OPT(n-1)，它们都是已知的。

接下来建立大问题和次大问题之间的关系。从次大问题转移到大问题可能存在两种情况：选择工作n和不选择工作n。

如果不选择工作n，问题就退化为求解OPT(n-1)。

如果选择工作n，要注意n可能与前面的工作不兼容。可能存在n与n-1冲突，或者n与n-2冲突，总之需要找到一个与n不冲突的工作，设p(j)为与工作j不冲突的最小序号的工作。如果整个集合中不存在与j相兼容的工作，那么p(j)=0。因此，选择工作n时，有OPT(n)=OPT(p(n))+vn。

取两者的最大值就得到OPT(n)的值，然后将n替换为j（其中j∈[1, n]），得到状态转移函数如下：

当j=0时：

当j大于0时：

通过以上状态转移函数的推导，解决示例题目得到：

得到：n=17，因此OPT(n)=50，最大权重为50。最优活动子集为3、6、12、15。

标签： 算法、 动态规划、 动态、

本文地址： https://yihaiquanyi.com/article/c8ebaaa5c31ff3a60685.html

上一篇：我憋了一肚子的话我是憋了一肚子话要说华为...
下一篇：iphone12promaxiPhone16Pro高清图曝光等等...