谁有动态规划的一些例题+解析 [复制链接]

谢谢了

#include<fstream>
using namespace std;
ifstream fin("medic.in");
ofstream fout("medic.out");
int t,m,ans;
int countline[1001];
struct data
{
  int time;
  int price;
}med[101];

main()
{
int indata();
int count();
indata();
count();
fout<<ans;
}

int indata()
{
int i;
fin>>t>>m;
for(i=1;i<=m;i++)
  fin>>med.time>>med.price;
}
int count()
{
int i,j,k;  
memset(countline,0,sizeof(countline)) ;
for(i=1;i<=m;i++)
  for(j=t;j>=1;j--)
    {
    if (j>=med.time&&med.price+countline[j-med.time]>countline[j])
      countline[j]=med.price+countline[j-med.time];
    }
ans=countline[t];
 
}

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);
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<a[j]) and (b[j]>max) then begin max:=b[j];p:=j end;
  if p<>0 then begin b:=b[p]+1;c:=p end
end;
max:=0;p:=0;
for i:=1 to n do
if b>max then begin max:=b;p:=i end;
writeln('maxlong=',max);
write('result is:');
while p<>0 do
begin write(a[p]:5);p:=c[p] end;
end.

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)+C，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,c);
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 then f[i,j]:=max(f[i-1,j-w]+c,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)+c} 当x>=w 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,c);
  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 then f:=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:=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)
  then begin b:=b[j]+a[i,j];c:=j end;
writeln('minlong=',b[1]);
x:=1;
while x<>0 do
  begin
  write(x:5);
  x:=c[x];
end;
end.