信息学 动态规划 习题
发布网友
发布时间：2022-04-29 22:24
共2个回答
热心网友
时间：2022-06-24 12:10
3.1 最长不降子序列
3.2 背包问题
3.3 最短路径
4.3 习题
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<i2<i3< … < ie 且有a(i1)<a(i2)< … <a(ie)则称为长度为e的不下降序列。如上例中3，18，23，24就是一个长度为4的不下降序列，同时也有3，7，10，12，16，24长度为6的不下降序列。程序要求，当原数列给出之后，求出最长的不下降序列。
（2）算法分析
根据动态规划的原理，由后往前进行搜索。
1· 对a(n)来说，由于它是最后一个数，所以当从a(n)开始查找时，只存在长度为1的不下降序列；
2· 若从a(n-1)开始查找，则存在下面的两种可能性：
①若a(n-1)<a(n)则存在长度为2的不下降序列a(n-1)，a(n)。
②若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]<a[j]) and (b[j]>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,...Cn/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<i<=n}
程序如下：（逆推法）
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]<b[i])
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.若城市路径示意图如下图所示:
图中，每条边上的数字是这段道路的长度。条件：从A地出发，只允许向右或向上走。试寻找一条从A地到B地的最短路径和长度。
2.求一个数列中的连续若干个数和的最大值.
3.资源分配问题:n个资源分配到m个项目上，i项目分配j个资源可获益a[i,j],求最大总效益。
4. 装箱问题
问题描述:有一个箱子容量为V（正整数，0＜＝V＜＝20000），同时有n个物品（0＜n＜＝30，每个物品有一个体积（正整数）。要求n个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。
样例
输入：
24 一个整数，表示箱子容量
6 一个整数，表示有n个物品
8 接下来n行，分别表示这n 个物品的各自体积
3
12
7
9
7
输出：
0 一个整数，表示箱子剩余空间。
或者下载动态规划的教程：
http://hi.baidu.com/111010000000/blog/item/69032531bc099f1deac4af46.html
热心网友
时间：2022-06-24 12:11
上Vijos上面有的。
