动态规划例题总结资料

《动态规划例题总结资料》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、动态规划习题总结【0-1背包】{题目}一个旅行者有一个最多能用M体积的背包，现在有N件物品，它们的体积分别是W1，W2，……,Wn,它们的价值分别为P1,P2，……,Pn.若每种物品只有一件求旅行者能获得最大总价值。{思路}f[i,v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值动态转移方程：f[i,v]=max{f[i-1,v],f[i-1,v-w[i]]+p[i]}边界条件：i=0或v<=0时f:=0｛样例｝输入：100577922222298750469990输出：133【最长不降字串】【导弹拦截】

2、{题目}设有整数序列b1,b2,b3,…,bm，若存在下标i1

3、拥有高效生产设备M台，准备分给下属的N个公司。各分公司若获得这些设备，可以为国家提供一定的盈利。问：如何分配这M台设备才能使国家得到的盈利最大？求出最大盈利值。其中M<=15，N<=10。分配原则：每个公司有权获得任意数目的设备，但总台数不得超过总设备数M。数据文件第一行保存两个数，第一个数是设备台数M，第二个数是分公司数N。接下来是一个M*N的矩阵，表明了第I个公司分配J台机器的盈利。{思路}f[i,j]表示前i个公司，分j台设备的最大盈利动归方程：f(i,j)=max{f(i-1,j-k)+v[i,k]}k=0,

4、1,…,j边界条件：k=0ori=0则f:=0{样例}输入：33304050203050202530输出：70【数字金字塔】{题目}数字塔一共有n层，第i层有i个数字，从最上面一个数字开始走，每向下一层时可以向左或向右走，最后的得分为所经过的数字和。请求出最大得分。{思路}f[i,j]表示在第i行第j个位置的最大得分动态转移方程：f[i,j]:=f[i-1,j-1]+num[i,j]{i=j}f[i,j]:=max(f[i-1,j],f[i-1,j-1])+num[i,j];{i<>j}边界条件：i=1f[i,j]:

5、=num[i,j]{样例}输入：5738810274445265输出：30【最短路径】{题目}求两点间的最短路径长度{思路}f(x)表示点x到y的最短路径长度动态转移方程：f(x)=min{f(i)+a[x,i]}a[x,i]>0,x

6、形三角剖分后所得到的最小乘积动态转移方程：F[I,J]=Min{F[I,K]+F[K,J]+S[I]*S[J]*S[K]}(0

7、系统。显然备用件越多，系统可靠性越高，但费用也越大，那么在一定总费用限制下，系统的最高可靠性等于多少？给定一些系统备用件的单价Ck，以及当用Mk个此备用件时部件的正常工作概率Pk（Mk），总费用上限C。求系统可能的最高可靠性。{思路}F[I,money]表示将money的资金用到前I项备用件中去的最大可靠性动态转移方程：F[I,money]=max{F[I-1,money–k*Cost[I]]*P[I,k](0<=I<=n,0<=K<=moneydivCost(I))边界条件：F[0,0]=0目标状态：F[n,C]{

8、样例}输入：22030.60.650.70.750.80.850.950.70.750.80.80.90.95输出：0.6375【石子合并】{题目}在一园形操场四周摆放N堆石子(N≤100),现要将石子有次序地合并成一堆.规定每次只能选相临的两堆合并成一堆,并将新的一堆的石子数,记为该次合并的得分。编一程序,由文件读入堆数N及每堆石子数(≤20