动态规划算法为什么需要最优子结构性质及子问题的重叠性

这个动态规划算法问题怎么解决啊?
Recall the greedy algorithm for Knapsack from the notes.
Show that, for every constant c < 2, there is an instance of Knapsack
for which the greedy algorithm produces a solution that is greater than
c times optimal. (Hint: recall the example given in class with capacity
19 with three items: u
1
with weight 11 and value 11.1, one with weight
10 and value 10, and one with weight 9 and value 9. In this case, the
optimal solution has value 19, whereas the greedy solution provides a
solution of value 11.1.)

急 1、实验项目名称：分治和动态规划算法实现 用c++ 或java 编写
实验项目1
1、x05实验项目名称：分治和动态规划算法实现
2、x05实验项目的目的和任务：
实验目的：加深对分治和动态规划算法原理及实现过程的理解.
实验任务：实现合并排序算法,用动态规划实现矩阵链乘法问题
3、实验内容：
(1) 利用合并排序算法对字符数组a[]={12,1,8,5,6,4,5}从小到大排序.
(2) 现在要求计算一个由8个矩阵组成的乘法,A1*A2* A3*A4* A5*A6* A7*A8.已知矩阵的维数如下,要求给矩阵添上七个括号使得基本乘法运算次数最少,并给出其运算次数.
A1：30*35
A2：35*25
A3：25*20
A4：20*30
A5：30*5
A6：5*30
A7：30*5
A8：5*25
4、考核方式：上交源代码和可执行程序

求“动态规划算法”在生物信息学中的应用一题
有哪位才子帮我解下面这道题：用动态规划算法比较ATTCG与TTGG两序列的同源性匹配,列出回溯路径上的矩阵元,并写出最佳匹配结果.
我以前没学过生物信息学,很着急用,重谢!