文档介绍：
实验三动态规划
算法 分析^p 与 设计 实验报告
学号
姓名
班级
上课地点
老师
上课时间
实验 三
动态规划 理解动态规划算法的主要设计思想和根本步骤；
掌握tln(“最长公共子序列为：”);
lcs (-1,-1,_,b);
}
实验结论
4 心得体会：
最长公共子序列比拟好理解哦。做起来也相较简单多了 3 3
0- -1 1 背包 问题
算法设计思想
(1) 分析^p 最优解：
设(y 1 ,y 2 ,...,y n )是所给 0-1 背包问题的一个最优解，那么 (y 2 ,...,y n )是下面相应子问题的一个最优解。
å=nii i _v2ma_
ïîïíì£ £ Î- £å=n i _y w C _ winii i2 }, 1 , 0 {1 12
(2)建立递归关系：
设所给 0-1 背包问题的子问题 å=ni kk k _v ma_
ïîïíì£ £ Σå=n k i _j _ wkni kk k}, 1 , 0 { 的最优值为 m(i，j)，即 m(i，j)是背包容量为 j，可选择物品为 i，i+1，...，n 时 0-1 背包问题的最优值。由 0-1 背包问题的最优子构造性质，可以建立计算 m(i，j)的递归式如下。
ii i iw jw jj i mv w j i m j i mj i m< £³îíì++ - + +=0 ) , 1 (} ) , 1 ( ), , 1 ( ma_{) , (
nn nw jw j vj n m< £³îíì=0 0) , (
〔3〕计算最优值：
public static void knapsack( int[] v, int[] w, n int t c, int[][] m)
{
int n = -1;
int jMa_ = (w[n]-1, c);
for( int j = 0; j j 有 m[n][j]=0
//m[n][j] 表示只有n物品，背包的容量为j时的最大价值
for ( int j = w[n]; j =1; i--)
{
jMa_ = (w[i]-1,c);
for( int j = 0; j= w[0])
m[0][c] = (m[0][c],m[1][c-w[0]]+v[0]);
.println(+m[0][c]);
}
〔4〕构造最优解：
public static void traceback( int[][] m, int[] w, int c, int[] _)
{// 根据最优值求出最优解
int n = -1;
for( int i = 0; i0)?1:0;
}
程序码 0 0- -1 1 背包问题 代码：
/__
_
下面是0-1的动态规划算法
_v[] w[] c 分别是价值、重量、和背包容量数组
_m[i][j]表示有i~n个物品，背包容量为j的最大价值。
_
***@author zhanling_ia
_/
public class beibao {
public static void knapsack( int[] v, int[] w, int c, int[][] m)
{
int n = -1;
int jMa_ = (w[n]-1, c);
for( int j = 0; j j 有 m[n][j]=0
//m[n][j] 表示只有n物品，背包的容量为j时的最大价值
for ( int j = w[n]; j =1; i--)
{
jMa_ = (w[i]-1,c);
for( int j = 0; j= w[0])
m[0][c] = (m[0][c],m[1][c-w[0]]+v[0]);
.println(+m[0][c]);
}
public static void traceback( int[][] m, int[] w, int c, int[] _)
{// 根据最优值求出最优解
int n = -1;
for( int i = 0; i0)?1:0;
}
public static vo