动态规划

一．用动态规划方法手工求解以下问题：有8万元的投资可以投给3个项目，每个项目在不同投资数额下（以万元为单位）的利润如下表。投资额盈利项目012345678项目105154080909598100项目20515406070737475项目30426404550515253请安排投资计划，使总的利润最大。写出你所设的状态变量、决策变量、状态转移方程与递推关系式，和手工求解的详细步骤及结果。设状态变量kx表示投资给项目k至项目n的投资额。决策变量ku表示投资给项目k的投资额，则状态转移方程为：1kkkxxu其中1kx表示投资给项目1k至项目n的投资额。允许决策集合：(){|0}kkkkkDxuux()kkfx表示把kx的钱投资给项目k至项目n，盈利的最大额。递推关系式：其中()kkgu表示上表格中项目k的投资额为ku时盈利。10()max{()()}1,......,1()()kkkkkkkkkuxnnnnfxgufxuknfxgx针对这个例子，3n，kx最大取8手工详解过程：1）初始化3k333333333(0)0;(1)4;(2)26;(3)40;(4)45;(5)50;(6)51;(7)52;(8)53fffffffff2）2k223223232232323223232323(0)max{(0)(0)}0(1)max{(0)(1),(1)(0)}max{04,50}5(2)max{(0)(2),(1)(1),(2)(0)}max{026,54,150}26(3)max{(0)(3),(1)(2),(2)(1),(3)(0)}fgffgfgffgfgfgffgfgfgfgf2232323232322323232323max{040,526,154,400}40(4)max{(0)(4),(1)(3),(2)(2),(3)(1),(4)(0)}max{045,540,1526,404,600}60(5)max{(0)(5),(1)(4),(2)(3),(3)(2),(4)(1)fgfgfgfgfgffgfgfgfgfgf232232323232323232,(5)(0)}max{050,545,1540,4026,604,700}70(6)max{(0)(6),(1)(5),(2)(4),(3)(3),(4)(2),(5)(1),(6)(0)}max{051,550,1545,4040,6026,704,730}86(7)mgffgfgfgfgfgfgfgff232323232323232322323232ax{(0)(7),(1)(6),(2)(5),(3)(4),(4)(3),(5)(2),(6)(1),(7)(0)}max{052,551,1550,4045,6040,7026,734,740}100(8)max{(0)(8),(1)(7),(2)(6),gfgfgfgfgfgfgfgffgfgfgfg32323232323(3)(5),(4)(4),(5)(3),(6)(2),(7)(1),(8)(0)}max{053,552,1551,4050,6045,7040,7326,744,750}110fgfgfgfgfgf3）1k112112121121212112121212(0)max{(0)(0)}0(1)max{(0)(1),(1)(0)}max{05,50}5(2)max{(0)(2),(1)(1),(2)(0)}max{026,55,150}26(3)max{(0)(3),(1)(2),(2)(1),(3)(0)}fgffgfgffgfgfgffgfgfgfgf1121212121211212121212max{040,526,155,400}40(4)max{(0)(4),(1)(3),(2)(2),(3)(1),(4)(0)}max{060,540,1526,405,800}80(5)max{(0)(5),(1)(4),(2)(3),(3)(2),(4)(1)fgfgfgfgfgffgfgfgfgfgf121121212121212121,(5)(0)}max{070,560,1540,4026,805,900}90(6)max{(0)(6),(1)(5),(2)(4),(3)(3),(4)(2),(5)(1),(6)(0)}max{086,570,1560,4040,8026,905,950}106(7)gffgfgfgfgfgfgfgff12121212121212121121212max{(0)(7),(1)(6),(2)(5),(3)(4),(4)(3),(5)(2),(6)(1),(7)(0)}max{0100,586,1570,4060,8040,9026,955,980}120(8)max{(0)(8),(1)(7),(2)(6),gfgfgfgfgfgfgfgffgfgfgf121212122212(3)(5),(4)(4),(5)(3),(6)(2),(7)(1),(8)(0)}max{0110,5100,1586,4070,8060,9040,9526,985,1000}140gfgfgfgfgfgf最终结果：给项目1投资4万元，项目2投资4万元，项目3不投资，将获得最大利润140万元二．用动态规划方法编程求解下面的问题：一凸8边形P的顶点顺时针为128{,,...,}vvv，任意两顶点间的线段的权重由矩阵D给出。若iv与jv是P上不相邻的两个顶点，则线段ijvv称为P的一条弦。求P得一个弦的集合T，使得T中多有的弦恰好将P分割成互不重迭的三角形，且各三角形的权重之和为最小(一个三角形的权重是其各边的权重之和)。要求：写出递推关系式、伪代码和程序的相关说明，并分析时间复杂度。(请遵守第一节课提出的有关assignment的要求：提交的可执行程序必须能够输出结果，源代码必须可编译等等)定义[][],1tijijn为凸子多边形1{,,...,}iijvvv的最优划分所对应的权值，即最优值。设退化的多边形1{,}iivv具有权值0。要计算的凸(n+1)边形的最有权值为[1][]tn。[][]0,1,2,...,tiiin。当1ji时，凸子多边形1{,,...,}iijvvv至少有三个顶点。由最有子结构的性质，[][]tij的值应为[][]tik的值加上[1][]tkj的值，再加上三角形1ikjvvv的权值。递推关系式：10min{[][][1][]()}[][]ikjikjtiktkjwvvvijtijjj伪代码：minWeight()1fori←1ton2do[i][i]←03forr←2ton4dofori←1ton-r+15doj←i+r-1;6t[i][j]←t[i+1][j]+w(i-1,i,j);7fork←i+1toj-18domin←t[i][k]+t[k+1][j]+w(i-1,k,j);9ifmint[i][j]10thent[i][j]←min;11returnt[1][n]程序：#includestdio.h#defineN20intm[N][N];intw(inti,intj,intk){returnm[i][j]+m[i][k]+m[j][k];}voidminWeight(intn,intt[][N]){inti,j,k,r,min;for(i=1;i=n;i++)t[i][i]=0;for(r=2;r=n;r++)for(i=1;i=n-r+1;i++){j=i+r-1;t[i][j]=t[i+1][j]+w(i-1,i,j);for(k=i+1;ki+r-1;k++){min=t[i][k]+t[k+1][j]+w(i-1,k,j);if(mint[i][j])t[i][j]=min;}}printf(%d\n,t[1][n]);}intmain(){intn,i,j;intt[N][N];scanf(%d,&n);for(i=0;in;i++)for(j=i+1;jn;j++)scanf(%d,&m[i][j]);minWeight(n-1,t);return0;}这个例子的最终输出结果为277。算法空间复杂度2()On，时间复杂度3()On。