老师所给的实验题目索引如下

实验二.动态规划算法←

基本题一 最长公共子序列问题

一、实验目的与要求

1、熟悉最长公共子序列问题的算法;

2、初步掌握动态规划算法;

二、实验题

若给定序列X={x1,x2,…xm},则另一序列Z={z1,z2,…zk}，是X的子序列是指存在一个严格递增下标序列{i1,i2,…ik}使得对于所有j=1,2…k有:zj=xij。例如，序列Z={B, C, D, B}是序列X={A, B, C, B, D, A, B}的子序列，相应的递增下标序列为{2, 3, 5，7}。

给定2个序列X和Y,当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。

给定2个序列X={x1,x2,…xm}和Y={y1,y2,…yn}，找出X和Y的最长公共子序列。

基本题二:最大字段和问题

一、实验目的与要求

1、熟悉最长最大字段和问题的算法;

2、进一步掌握动态规划算法;

二、实验题

若给定n个整数组成的序列a1，a2, a3…

求该序列形如a1+a2+a3+…..+an的最大值。

提高题一:用动态规划法求解0/1 背包问题

一、实验要求与目的

1、掌握动态规划算法求解问题的一般特征和步骤。

2、使用动态规划法编程，求解0/1背包问题。

二、实验内容

1、问题描述:给定n种物品和一个背包，物品i的重量是W; 其价值为V，问如何选择装入背包的物品，使得装入背包的物品的总价值最大?

2、算法描述。

3、程序实现;给出实例测试结果。