动态规划算法实验报告
- 格式：doc
- 大小：232.08 KB
- 文档页数：7
1 南京信息工程大学 滨江学院 实验（实习）报告
1. 实验目的
动态规划通常用来求解最优化问题。通过本次实验掌握动态规划算法。通过矩阵连乘问题和0-1背包问题实现动态规划算法。学会刻画问题的最优结构特征，并利用最优化问题具有的重叠子问题性质，对每个子问题求解一次，将解存入表中，当再次需要这个子问题时直接查表，每次查表的代价为常量时间。
2. 实验内容及分析设计过程
1. 矩阵链乘法问题
矩阵链乘法问题可描述如下：给定个矩阵的链,矩阵的规模为，求完全括号方案，使得计算乘积所需的标量乘法次数最少。
令m[i,j]表示计算矩阵所需标量乘法次数的最小值，那么，原问题的最优解计是m[1,n］。
最小代价括号化方案的递归求解公式为
采用自底向上表格法代替上述递归算法来计算最优代价。
为了实现自底向上方法，我们必须确定计算m[i,j]时需要访问哪些其他表项。上述公式显示，
j-i+l 个矩阵链相乘的最优计算代价m[i,j] 只依赖于那些少于j-i+l 个矩阵链相乘的最优计算代价。因此，算法应该按长度递增的顺序求解矩阵链括号化问题，并按对应的顺序填写表m。
对如下输入
A1 A2 A3 A4 A5 A6
3035 3515 155 510 1020 2025
程序运行结果为
2. 背包问题
2 给定n个重量为价值为的物品和一个承重为W的背包。求这些物品中最有价值的一个子集，并且要能装到背包中。
设V[i,j]是能够放进承重量为j的背包的前i个物品中最有价值子集的总价值。则递推关系为
初始条件V[0,j]=0(j>=0),V[i,0]=0(i>=0)
我们的目标是求V[n，W]。递归式给出了V[i,j]的计算顺序，V[i,j]只依赖与前一行的那些项。故可以逐行计算V[i,j].
对于物品数量n=5，w[n]={2,2,6,5,4},v[n]={6,3,5,4,6},背包总重量c=10
程序运行结果为
3. 实验小结
通过本次实验加深了我对动态规划算法的理解。而且对动态规范编写代码解决一个实际问题有了进一步的认识。即当算法考虑的原问题的每一个子问题，算法都需要计算一个最优解。换句话说，所有算法生成的表项表示算法考虑的子问题的最优解。这时候用动态规范把每一个最优解求出来（利用递归公式），就能够保证最后求得的一定是最优解。
附录
1. 矩阵链乘问题
MatrixChainTest.java
public class MatrixChainTest
{
public static void main(String [] args)
{
int p[]={30,35,15,5,10,20,25};
MatrixChain mc=new MatrixChain(p);
mc.solve();
}
}
class MatrixChain
3 {
private int m[][];
private int s[][];
public int p[];
public MatrixChain(int [] p0)
{
p=p0;
}
public void solve()
{
m=new int[p.length][p.length];
s=new int[p.length-1][p.length];
MatrixChainOrder();
System.out.printf("最少乘次数:%d\n",m[1][p.length-1]);
PrintOptimalParens(1, p.length-1);
System.out.println();
}
private void MatrixChainOrder()
{
int n=p.length-1;
for(int i=1;i<=n;i++)
{
m[i][i]=0;
}
for(int l=2;l<=n;l++)
{
for(int i=1;i<=n-l+1;i++)
{
int j=i+l-1;
m[i][j]=Integer.MAX_VALUE;
for(int k=i;k<=j-1;k++)
{
int q=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];
if(q
{
m[i][j]=q;
s[i][j]=k;
}
}
}
}
}
4 private void PrintOptimalParens(int i,int j)
{
if(i==j)
{
System.out.print("A"+i);
}
else
{
System.out.print("(");
PrintOptimalParens(i,s[i][j]);
PrintOptimalParens(s[i][j]+1,j);
System.out.print(")");
}
}
}
2. 背包问题
KnapsackTest.java
public class KnapsackTest
{
public static void main(String [] args)
{
int w[]={2,2,6,5,4};
int v[]={6,3,5,4,6};
int W0=10;
Knapsack ks=new Knapsack(w, v, W0);
ks.solve();
}
}
class Knapsack
{
int w[];//重量
int v[];//价值
int V[][];//V[i][j]表示物品0,1,...i放入限重j的背包所能获取的最大价值
int c[];//c[i]=0表示选择物品i,c[i]=0表示不选物品i
int W;//限重
public Knapsack(int w0[],int v0[],int W0)
{
w=w0;
v=v0;
5 W=W0;
}
private void MaximizeValue()
{
V=new int[w.length][W+1];
for(int j=0;j<=W;j++)
{
if(j>=w[0])
{
V[0][j]=v[0];
}
else
{
V[0][j]=0;
}
}
for(int i=0;i
{
V[i][0]=0;
}
for(int i=1;i
{
for(int j=1;j<=W;j++)
{
if(j>=w[i]&&((V[i-1][j-w[i]]+v[i])>V[i-1][j]))
{
V[i][j]=V[i-1][j-w[i]]+v[i];
}
else
{
V[i][j]=V[i-1][j];
}
}
}
}
private void Choose(int i,int j)
{
if(i==0)
{
if(j>=w[0])
c[0]=1;
else
c[0]=0;
6 return ;
}
if(V[i][j]!=V[i-1][j])
{
c[i]=1;
Choose(i-1,j-w[i]);
}
else
{
c[i]=0;
Choose(i-1,j);
}
}
public void solve()
{
MaximizeValue();
// for(int i=0;i
// {
// for(int j=0;j<=W;j++)
// {
// System.out.printf("%d ",V[i][j]);
// }
// System.out.printf("\n");
// }
System.out.printf("最大价值:%d\n",V[w.length-1][W]);
c=new int[w.length];
Choose(w.length-1,W);
System.out.printf("选择的物品:");
for(int i=0;i
