动态规划.doc

一．用动态规划方法手工求解以下问题：
有 8 万元的投资可以投给3 个项目，每个项目在不同投资数额下（以万元为单位）的利润如下表。
投资额
盈利
项目
0
1
2
3
4
5
一．用动态规划方法手工求解以下问题：
有 8 万元的投资可以投给3 个项目，每个项目在不同投资数额下（以万元为单位）的利润如下表。
投资额
盈利
项目
0
1
2
3
4
5
6
7
8
项目1
0
5
15
40
80
90
95
98
100
项目2
0
5
15
40
60
70
73
74
75
项目3
0
4
26
40
45
50
51
52
53
请安排投资计划，使总的利润最大。
写出你所设的状态变量、决策变量、状态转移方程与递推关系式，和手工求解的详细步
骤及结果。
设状态变量表示投资给项目至项目的投资额。
决策变量表示投资给项目的投资额，则状态转移方程为： 其中表示投资给项目至项目的投资额。
允许决策集合：
表示把的钱投资给项目至项目，盈利的最大额。
递推关系式：
其中表示上表格中项目的投资额为时盈利。
针对这个例子，，最大取8
手工详解过程：
1）初始化
2）
3）
最终结果：给项目1投资4万元，项目2投资4万元，项目3不投资，将获得最大利润140万元
二．用动态规划方法编程求解下面的问题：
一凸8边形P的顶点顺时针为，任意两顶点间的线段的权重由矩阵D给出。若与是P上不相邻的两个顶点，则线段称为P的一条弦。求P得一个弦的集合T，使得T中多有的弦恰好将P分割成互不重迭的三角形，且各三角形的权重之和为最小(一个三角形的权重是其各边的权重之和)。
要求：写出递推关系式、伪代码和程序的相关说明，并分析时间复杂度。(请遵守第一节课提出的有关assignment的要求：提交的可执行程序必须能够输出结果，源代码必须可编译等等)
定义为凸子多边形的最优划分所对应的权值，即最优值。设退化的多边形具有权值0。要计算的凸(n+1)边形的最有权值为。
。当时，凸子多边形至少有三个顶点。由最有子结构的性质，的值应为的值加上的值，再加上三角形的权值。
递推关系式：
伪代码：
minWeight()
1 for i ←1 to n
2 do [i][i] ←0
3 for r←2 to n
4 do for i ←1 to n-r+1
5 do j←i+r-1;
6 t[i][j] ←t[i+1][j]+w(i-1,i,j);
7 for k←i+1 to j-1
8 do min←t[i][k]+t[k+1][j]+w(i-1,k,j);
9 if min<t[i][j]
10 then t[i][j] ←min;
11 return t[1][n]
程序：
#include<>