C++动态规划最优解问题



动态规划：用来解决最优化问题
思想：把走过的路记下来，下次走时直接拿来用，以节省时间。
方法：从后向前建立记忆数组，把最优化判断转化成记忆数组的判断。
原理：局部最优，整体最优。
（建立记忆数组）
1.魔法课

哈里波特终于离开了可怕的舅舅家，来到了Hogwarts的魔法学校学习魔法。魔法的世界是多么的神奇，小哈利对一切都充满了好奇。他想尽可能多的学习魔法。现在的问题是有些魔法课的时间有冲突，哈利无法在一天内上所有的魔法课。所以需要你写一个程序来帮助哈里波特制定一个学习计划，来安排第一天的学习，使得他能尽可能地上更多的魔法课。注意，上课的时间是不能改变的。而且上课的时候不能迟到也不能早退，否则魔法老师会对哈利产生不满。可以假设从一个教室到另一个教室的时间短得忽略不计。另外，在Hogwarts的魔法世界里，是不使用24小时制的计时方法的，它只是简单的使用一个整数来表示当时的时间。

输入：每个测试数据开头是一个整数n（1<=n<=1000），表示魔法课的总数。接下来n行，每行包括两个正整数s、t，分别表示该魔法课的上课时间和下课时间。其中s<t。

输出：对于每个测试数据，在单独一行内输出哈利所能上的最多魔法课数。

样例：

输入（plan.in）：

      3

1  15


2  19

15  17

输出（plan.out）：

  2

?/P>

?/P> 解：
  n=3      

 开课时间：1   下课时间：15
 开课时间：2   下课时间：19
 开课时间：15   下课时间：17
                                                                                         

#include<iostream.h>
#define max 1000
int a[max][2];//开课，结束时间
int num[max];//记忆数组
void main()
{
int n;
cin>>n;
for(int i=0;i<n;i++)
cin>>a[i][0]>>a[i][1];//读入开课时间，结束时间
//填记忆数组
num[n-1]=1;//填最后一门课
int max2;
for(i=n-2;i>=0;i–)//从后向前填记忆数组
{
max2=0;//找记忆数组的最大值
for(int j=i+1;j<n;j++)//从后向前找最大
if((a[i][1]<=a[j][0])&&(num[j]>max2))//可以连接并且最大
max2=num[j];
num[i]=max2+1;//填第i门课的记忆数组
}
int max3;
for(i=0;i<n;i++)
if(num[i]>max3)
max3=num[i];
cout<<max3;
}