运筹学里面的。
[email protected]
[email protected]
解决方案 »
- 用Delphi写了个计算文件MD5、SHA-1、SHA-256哈希值的小工具
- 查询后排序的问题
- 不能存取文件的问题 用adoconnection连接odbc,odbc为microsoft visual foxpro driver,连接vfp自由表,delphi程序向表追加完记录后,用vf
- 怎样将数据库中的每条记录分别做成一个报表打印呢?(delphi 7.0)
- 请教高手Delphi中的窗体释放怎么解决?
- 为什么用ADOTable删除数据课中的数据时总报错?
- Web Service 里面的如何操纵cookie?
- 怎样取得当前日期——>'2003-05-31',并往前推算出50天的日期?(80分)谢谢!
- 关于如何把图片放到数据库里面????
- 请教各位前辈,如何控制鼠标只能在dbgrid中的一个单元格中移动,如果控制在其他控件上,则为clipcursor(控件名称.boundsrect),但dbgrid的某一个单元格如何来引用呢?
- 急!!(一个游戏问题:关于人机对话的问题?)
- 简单问题
//for i := 1 to n do
//Dist[i][i] = MAX;
for k := 1 to n do
for i := 1 to n do
for j := 1 to n do
if (Dist[i][j] > Dist[i][k] + Dist[k][j]) and (k <> i) and (j <> i) and (i <> j) then
begin
Dist[i][j] = Dist[i][k] + Dist[k][j];
并且记下从i到j的路径序列;
end;好像是这样的哦,可以求任意两点的最短路径,我记不太清楚了
动态规划算法,其基本思想是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。
适合于用动态规划求解的问题,经分解得到子问题都是相关的。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到,只要它被计算过,就将其结果填入表中。这就是动态规划法的基本思路 。
{a1} {b1} {c1} {d1}
start->{a2} {b2} {c2} {d2} -> end
{a3} {b3} {c3} {d3}
(a与b,b与c,c与d 的各点均向连,图不好画,知道意思就行,从start -> end 中间必进过 a b c d 其中各一点,找最短的一条路。)
注意: 如果abcd的连接不是这样的有序(比如a中有连到c的线路)。那就不是用动态规划,就要用图论中的Dijkstra 算法或 Floyd 算法了。
现在是具体做一个。。
例: a1->b1 10 ; a2->b1 20 ; a3->b3 30 ;a2->b2 40 ;
b1->c1 100; b2->c2 200 ; b3->c3 300 ; b2->c1 400 ;
c1->d2 4 ; c2->d1 3 ; c2->d3 2 ; c3->d2 1 ;
(在纸上把图画好就方便了。)
分析过程 :要从后往前
先看 c->d : 从c1->d最短是c1->d2 4 ;
从c2->d最短是c2->d3 2 ;
从c3->d最短是c3->d2 1 ;
再看 b->c->d :此时只要把c1,c2,c3的最短的标在c1,c2,c3上,与b->c的相加。就是从b->c->d的最短路。
从b1->d 最短b1->c1->d2 104 ;
从b2->d 最短b2->c2->d3 202 ;
从b3->d 最短b3->c3->d2 301 ;
同样 :
从a1->d 最短a1->b1->c1->d2 114 ;
从a2->d 最短a2->b1->c1->d2 124 ;
从a3->d 最短a3->b3->c3->d2 331 ;
最短就是 a1->b1->c1->d2 了。。写了一堆,也不知道能不能看明白。。
再附一个题目和求解。
旅行
提交文件名:tEWeLeyte〖问题描述〗
GDOI队员们到Z镇游玩。Z镇是一个很特别的城镇,它有m+1条东西方向和n+1条南北方向的道路,划分成m*n个区域。Z镇的名胜位于这些区域内。从上往下数第i行,从左往右数第j列的区域记为D(i,j)。GDOI队员们预先对这m*n个区域打分V(i,j)(分数可正可负)。分数越高表示他们越想到那个地方,越低表示他们越不想去。为了方便集合,队员们只能在某一范围内活动。我们可以用(m1,nl)与(m2,n2)(m1<=m2,n1<=n2)表示这样的一个范围:它是这些区域的集合:{D(i,j)|m1<=I<=m2,n1<=j<=n2}。GDOI队员们希望他们活动范围内的区域的分值总和最大。
当然,有可能队员们一个地方也不去(例如,所有区域的分值都是负数。当然,如果某范串内的分值总和为零的话,他们也会去玩)。也有可能他们游览整个Z镇。你的任务是编写一个程序,求出他们的活动范围(m1,nl),(m2,n2〉。〖输入格式〗
输入数据存放在当前目录下的文本文件"travel.dat"中。数据有m+1行。第一行有两个数m,n(m,n定义如上)。其中,(1<=m<=250,1<=n<=250)。接下来的m行,每行n个整数,第i行第j个数表示分值V(i,j)(-128<=V(i,j)<=l27)。每两个数之间有一个空格。〖输出格式〗
答案输出到当前目录下?quot;travel.out"中,只有一行,分两种情况:
1.队员们在范围(m1,n1),(m2,n2)内活动,输出该范围内的分值。
2.队员们不想去任何地方,只需输出"NO"。
注意:不要有多余空行,行首行尾不要有多余空格。
〖输入输出举例〗样例一
Travel.dat
4 5
1 -2 3 -4 5
6 7 8 9 10
-11 12 13 14 -15
16 17 18 19 20travel.out
146样例二
Travel.dat
2 3
-1 -2 -1
-4 -3 -6travel.out
no 〖问题分析〗
我们先看一个比较简单的问题,如何在一个队列里找出连续的几个数,使数的总和最大。对于这样的问题,我们可以用动态规划来做,即max=max{max(a[i-1])+a[i],a[i]};具体到了这道题,就可以将连续的几行合并起来,转化为以上的问题。而如果我们直接搜索,就需要6层for循环。具体流程如下:
for i:=1 to m do
for j:=i to m do
for k:= 1 to n do
begin
for l:=i to j do
合并行;
求max值;
end;
程序基本上就是这样,但要注意:max值一定要设为longint ,否则测试时将会有一半以上的数据出错!!〖数据结构〗
一个用于读数据的250*250的数组(注意类型要设为shortint),及一个250的一维数组(用于合并行);
优缺点及改进办法:这个程序最大的缺点就是搜索量太大,有些数据可能会超时。通过观察我们会发现:在合并i到j行与合并i到j+1行时,只是在原有合并好的数组上再加一行,无须重新计算,因此,程序可改进如下:
for i:=1 to m do
for j:=i to m do
for k:= 1 to n do
begin
b[k];=a[j,k]+b[k];{b是合并好的数组,a蔷卣髛
求max值;
end;
经过改进后,程序在所有的测试数据上都能通过(小于2秒),这道题就算完成了。 〖参考程序〗
program travle;
var f,P:text;
m,n,i,j,k,l,t:integer;
max,maxest:longint;
pan:boolean;
b:array[1.. 250] of longint;
a:array[1..250,1..250] of shortint;
procedure input;
begin
assign(f,'travel7.dat');
reset(f);
read(f,m);
readln(f,n);
pan:=true;
for i:=1 to m do
begin
for j:=1 to n do
read(f,a[i,j]);
if a[i,j]>=0 then pan:=false;
readln(f);
end;
close(f);
end;
procedure search;
begin
for i:=1 to m do
begin
for j:=i to m do
begin
max:=0;
for l:=1 to n do
begin
b[l]:=a[j,l]+b[l];
if max+b[l]>b[l] then max:=max+b[l]
else max:=b[l];
end;
if max>maxest then maxest:=max;
end;
for j:=1 to n do
b[j]:=0;
end;
end;
procedure output;
begin
assign(p,'u:\travle.out');
rewrite(p);
if pan then writeln(p,'No')
else writeln(p,maxest);
close(p);
end;
begin
input;
search;
output;
end.