pascal动态规划.ppt

下篇
02 八月 2017
1
[三]经典例题讲解
『例3』接苹果
[题意简述]
农场的夏季是收获的好季节。在John的农场,他们用一种特别的方式来收苹果:Bessie摇苹果树,苹果落下,然后John尽力接到尽可能多的苹果。作为一个有经验的农夫,John将这个过程坐标化。他清楚地知道什么时候(1<=t<=1,000,000)什么位置(用二维坐标表示,-1000<=x,y<=1000)会有苹果落下。他只有提前到达那个位置,才能接到那个位置掉下的苹果。一个单位时间,John能走s(1<=s<=1000)个单位。假设他开始时(t=0)站在(0,0)点,他最多能接到多少个苹果?
02 八月 2017
2
[三]经典例题讲解
『例3』接苹果
[输入格式]
第一行为两个整数N(苹果个数,N<=5000)和S(速度);
第2..N+1行:每行有三个整数Xi,Yi,Ti,表示每个苹果掉下的位置和落下的时间。
[输出格式]
输出仅一行为一个数,表示最多能接到几个苹果。
02 八月 2017
3
[三]经典例题讲解
『例3』接苹果
[输入样例]
5 3
0 0 1
0 3 2
-5 12 6
-1 0 3
-1 1 2
[输出样例]
3
(说明:John可以接到第1,5,4个苹果。)
02 八月 2017
4
[三]经典例题讲解
02 八月 2017
5
0
1
2
3
4
5
(Xi,Yi)
(0,0)
(0,0)
(0,3)
(-1,1)
(-1,0)
(-5,12)
Ti
0
1
2
2
3
6
f[i]
0
『算法分析与设计』
[数据结构]
f[i]表示恰好接到第i个苹果时所能获得的最多的苹果数;
Ti表示每个苹果对应的下落时刻。
[三]经典例题讲解
02 八月 2017
6
0
1
2
3
4
5
(Xi,Yi)
(0,0)
(0,0)
(0,3)
(-1,1)
(-1,0)
(-5,12)
Ti
0
1
2
2
3
6
f[i]
0
1
2
2
3
3
『算法分析与设计』
[算法实现]
(1)以按先后顺序落下的苹果为阶段,从第一项起,只需做一次比较,因位置恰好在(0,0),故可以接到此苹果,f[1]为1。
(2)第二项前面有两种选择,因此需要做两次比较,(0,0)到(0,3)的距离仅有3<=(2-1)*3,故f[2]为2,依次类推,得如下表:
[三]经典例题讲解
『算法分析与设计』
①划分阶段:以按先后顺序落下的苹果为阶段。
②确立状态及状态变量:n个苹果全部落下后接到的最多苹果数。
③决策:选择前面哪个苹果,接完来得及接这个苹果。
④策略和最优策略:最终解在哪儿。
⑤状态转移方程:
F(i)=max{F(j)+1}
其中:0<=j<=i-1,且dis(i,j)<=(time(i)-time(j))*S
02 八月 2017
7
[三]经典例题讲解
『参考程序片段』
//Pascal代码
f[0]:=0; ans:=0; if f[i]>ans then ans:=f[i];
for i:=1 to n do //dp end;
begin
f[i]:=0;
for j:=0 to i-1 do
if (j=0) or ((j<>0) and (f[j]<>0)) then
begin
m:=dis(i,j);
if (m<=s*(app[i].time-app[j].time)) and
(f[j]+1>f[i]) then f[i]:=f[j]+1;
end;
02 八月 2017
8
[三]经典例题讲解
『参考程序片段』
//C++代码
f[0]=0; ans=0; if (f[i]>ans) ans=f[i];
for (i=1;i<=n;i++) //dp }
{
f[i]=0;
for (j=0;j<=i-1;j++)
if (j==0||(j!=0&&f[j]!=0))
{
m=dis(i,j);
if (m<=s*(app[i].time-app[j].time)
&& f[j]+1>f[i]) f[i]=f[j]+1;
}
02 八月 2017
9
[三]经典例题讲解
『小结』
排序是使用动态规划过程中的重要手段之一。有些问题初看不具有最优子结构,但经过恰当的排序之后,便可使用动态规划解决了。
02 八月 2017
10