题目要求：
求区间图的最大加权独立集。（选择一部分互不重叠的区间，使得被选出来的区间权重之和最大）
图一
题目分析：
这类问题可以归结为区间调度问题，这是其中最普通的一类，即加权最大区间调度问题，其求解思路可以通过求最多区间调度（贪婪算法dp[i-1] = dp[i]），无权最大区间（权值为1的动态规划）依次发展过来，其具体思路分析详见http://blog.csdn.net/yutianzuijin/article/details/45116705#。我也从博客中转载了这篇文章，http://blog.csdn.net/lukas_sun/article/details/53770959。向原作者致敬！
题目求解：
求解最大权值区间的必要条件就是各最优区间互不冲突，这是这类调度问题共同的影子，只不过它的目标是让各区间的权值和最大。
和所有这种规划问题相同，我们需要对所有区间进行排序，排序原则为结束时间的先后，因为用开始时间排序无法得到各区间明确界限。
首先规定几个记号
O（j）： 需求区间{ 1……j }的最优解集
p ( n ): 最大的满足不与第n个区间冲突的区间号
OPT( j ): O( j )的最优解值。
由此定义可以分析得到第p(n)+1, p(n)+2 ,p(n)+3…………n-1个区间都与第n个区间冲突，所以O一定包含对需求区间{1，……p(n)}的最优解（否则可以将其替换成最优解而不影响需求区间n），由于p(n) <= n-1，所以如果n不包含在O里，则其可以转化为对需求区间 {1……n-1}的求解。
则我们的递推模型可以以是否选择第j个区间为构造依据。
按照此递推公式可知求解过程：
OPT（3）= 3 （2，3）
OPT（5）= 5+OPT（0）= 5 （1，5）
OPT（8）= 6+OPT（4）= 6 +OPT（3）= 9 （2，3）、（4，8）
OPT（10）= 1+OPT（9） = 1+OPT（8）=10 （2，3）、（4，8）、（9，10）
OPT（12）= 10+OPT（6）= 10+OPT（5）>10 =15
OPT（14）= 0+OPT（13）= OPT（12）= 15
OPT（15）= 7+OPT（11）= 7+OPT（10）= 17 >OPT( 14 )
OPT（17）= OPT（15）> = 12+OPT (7) = 17
OPT（18）= 4+OPT（16）= 4+OPT（15）= 21>OPT(17)
综上，该图最大权和为21，在其递归算法中的
判断条件后将所选的边加入到边的数组中，调用结束后输出这个数组可以得到所选边集：
{（2，3）（4，8）（9，10）（11，15）（16，18）}
若Max（）函数和递归判断中的”>”换为“>=”虽然使最大权值不变但可使所选边集发生变化，如此例中OPT（17）= 17，但所选边集为
{（1，5）（7，17）}
不同于改动前的边集：
{（2，3）（4，8）（9，10）（11，15）}
题目扩展：
这个问题可以转化为求最大加权独立集的问题，这种图论问题广泛应用于DNA测序等方面，且为NP问题，求解困难。即将每条线段转化为图中的一个顶点，将有重叠部分的线段设置为相邻的顶点，每条线段的权值在顶点数据中体现，则上述问题转换为选择图中不相邻的最大权值顶点集。转换后的图如图二所示。
图二
参考文献
《算法设计》第6章动态规划 Jon Kleinberg ,Eva Tardos清华大学出版社
《动态规划》ppt 姜海涛
附录
求最大权值部分实现代码
参考姚光超博主的代码实现
constintMAX_N=100000;
//输入
intN,S[MAX_N],T[MAX_N];
//用于对工作排序的pair数组
pair<int,int>itv[MAX_N];
voidsolve()
{
//对pair进行的是字典序比较，为了让结束时间早的工作排在前面，把T存入first，//把S存入second
for(inti=0;i<N;i++)
{
itv[i].first=T[i];
itv[i].second=S[i];
}
sort(itv,itv+N);
dp[0]=(itv[0].first-itv[0].second)*V[0];
for(inti=1;i<N;i++)
{
intmax;
//select the ithinterval
intnonOverlap=lower_bound(itv,itv[i].second)-1;
if(nonOverlap>=0)
max=dp[nonOverlap]+(itv[i].first-itv[i].second)*V[i];
else
max=(itv[i].first-itv[i].second)*V[i];
//do not selectthe ith interval
dp[i]=max>dp[i-1]?max:dp[i-1];
}
printf(“%d\n”,dp[N-1]);
}