动态规划的具体应用例题
- 格式：doc
- 大小：63.50 KB
- 文档页数：11
动态规划的具体应用例题
3.1 最长不降子序列
（1）问题描述
设有由n个不相同的整数组成的数列，记为:
a(1)、a(2)、……、a(n)且a(i)<>a(j) (i<>j)
例如3，18，7，14，10，12，23，41，16，24。
若存在i1
（2）算法分析
根据动态规划的原理，由后往前进行搜索。
1· 对a(n)来说，由于它是最后一个数，所以当从a(n)开始查找时，只存在长度为1的不下降序列；
2· 若从a(n-1)开始查找，则存在下面的两种可能性：
①若a(n-1)
②若a(n-1)>a(n)则存在长度为1的不下降序列a(n-1)或a(n)。
3· 一般若从a(i)开始，此时最长不下降序列应该按下列方法求出:
在a(i+1),a(i+2),…,a(n)中，找出一个比a(i)大的且最长的不下降序列，作为它的后继。 4.用数组b(i),c(i)分别记录点i到n的最长的不降子序列的长度和点i后继接点的编号
(3) 程序如下:（逆推法）
program li1;
const maxn=100;
var a,b,c:array[1..maxn] of integer;
fname:string;
f:text;
n,i,j,max,p:integer;
begin
readln(fname);
assign(f,fname);
reset(f);
readln(f,n);+
for i:=1 to n do
begin
read(f,a[i]);
b[n]:=1;
c[n]:=0;
end;
for i:= n-1 downto 1 do
begin max:=0;p:=0;
for j:=i+1 to n do
if (a[i]max) then begin max:=b[j];p:=j
end;
if p<>0 then begin b[i]:=b[p]+1;c[i]:=p end
end;
max:=0;p:=0;
for i:=1 to n do
if b[i]>max then begin max:=b[i];p:=i end;
writeln('maxlong=',max);
write('result is:');
while p<>0 do
begin write(a[p]:5);p:=c[p] end;
end.
3.2 背包问题
背包问题有三种
1.部分背包问题
一个旅行者有一个最多能用m公斤的背包，现在有n种物品，它们的总重量分别是W1，W2，...,Wn,它们的总价值分别为C1,C2,...,Cn.求旅行者能获得最大总价值。
解决问题的方法是贪心算法:将C1/W1,C2/W2,/Wn,从大到小排序,不停地选择价值与重量比最大的放人背包直到放满为止. 2.0/1背包
一个旅行者有一个最多能用m公斤的背包，现在有n件物品，它们的重量分别是W1，W2，...,Wn,它们的价值分别为C1,C2,...,Cn.若每种物品只有一件求旅行者能获得最大总价值。
<1>分析说明:
显然这个题可用深度优先方法对每件物品进行枚举(选或不选用0,1控制).
程序简单,但是当n的值很大的时候不能满足时间要求，时间复杂度为O（2n）。按递归的思想我们可以把问题分解为子问题,使用递归函数
设 f(i，x)表示前i件物品，总重量不超过x的最优价值
则 f（i，x）=max(f(i－1，x-W[i])+C[i]，f（i－1，x））
f（n，m）即为最优解，边界条件为f（0，x）＝0 ，f(i,0)=0;
动态规划方法(顺推法)程序如下:
程序如下：
program knapsack02;
const maxm=200;maxn=30;
type ar=array[1..maxn] of integer;
var m,n,j,i:integer;
c,w:ar;
f:array[0..maxn,0..maxm] of integer;
function max(x,y:integer):integer; begin
if x>y then max:=x else max:=y;
end;
begin
readln(m,n);
for i:= 1 to n do
readln(w[i],c[i]);
for i:=1 to m do f(0,i):=0;
for i:=1 to n do f(i,0):=0;
for i:=1 to n do
for j:=1 to m do
begin
if j>=w[i] then
f[i,j]:=max(f[i-1,j-w[i]]+c[i],f[i-1,j])
else f[i,j]:=f[i-1,j];
end;
writeln(f[n,m]);
end.
使用二维数组存储各子问题时方便，但当maxm较大时如maxn=2000时不能定义二维数组f,怎么办,其实可以用一维数组,但是上述中j:=1 to m 要改为j:=m downto 1,为什么?请大家自己解决。
3.完全背包问题 一个旅行者有一个最多能用m公斤的背包，现在有n种物品，每件的重量分别是W1，W2，...,Wn,
每件的价值分别为C1,C2,...,Cn.若的每种物品的件数足够多.
求旅行者能获得的最大总价值。
本问题的数学模型如下：
设 f(x)表示重量不超过x公斤的最大价值，
则 f(x）=max{f(x-w[i])+c[i]} 当x>=w[i] 1<=i<=n
程序如下:（顺推法）
program knapsack04;
const maxm=2000;maxn=30;
type ar=array[0..maxn] of integer;
var m,n,j,i,t:integer;
c,w:ar;
f:array[0..maxm] of integer;
begin
readln(m,n);
for i:= 1 to n do
readln(w[i],c[i]);
f(0):=0;
for i:=1 to m do
for j:=1 to n do
begin if i>=w[j] then t:=f[i-w[j]]+c[j];
if t>f[i] then f[i]:=t
end;
writeln(f[m]);
end.
3.3 最短路径
问题描述：
如图：求v1到v10的最短路径长度及最短路径。
图的邻接矩阵如下：
0 2 5 1 -1 -1 -1 -1 -1 -1
-1 0 -1 -1 12 14 -1 -1 -1 -1
-1 -1 0 -1 6 10 4 -1 -1 -1
-1 -1 -1 0 13 12 11 -1 -1 -1 -1 -1 -1 -1 0 -1 -1 3 9 -1
-1 -1 -1 -1 -1 0 -1 6 5 -1
-1 -1 -1 -1 -1 -1 0 -1 10 -1
-1 -1 -1 -1 -1 -1 -1 0 -1 5
-1 -1 -1 -1 -1 -1 -1 -1 0 2
-1 -1 -1 -1 -1 -1 -1 -1 -1 0
采用逆推法
设f（x）表示点x到v10的最短路径长度
则 f(10)=0
f(x)=min{ f(i)+a[x,i] 当a[x,i]>0 ,x
程序如下：（逆推法）
program lt3;
const n=10;
var
a:array[1..n,1..n] of integer;
b,c:array[1..n] of integer;
fname:string;
f:text;
i,j,x:integer;
begin
readln(fname);
assign(f,fname); reset(f);
for i:=1 to n do
for j:=1 to n do
read(f,a[i,j]);
close(f);
for i:=1 to n do
b[i]:=maxint;
b[n]:=0;
for i:= n-1 downto 1 do
for j:=n downto i+1 do
if (a[i,j]>0) and (b[j]<>maxint) and (b[j]+a[i,j]
then begin b[i]:=b[j]+a[i,j];c[i]:=j end;
writeln('minlong=',b[1]);
x:=1;
while x<>0 do
begin
write(x:5);
x:=c[x];
end;
end.
3.4习题
1.若城市路径示意图如下图所示:
