动态规划算法作业.pdf

1n←length(T)2createarrayx[1:L]3forj←1toL4dox[j]←j/T[1]5fori←2ton6doforj←Lto17dofork←1toj/T[i]8doifx[j-k*x]+kx[j]9thenx[j]←x[j-k*x]+k10returnx时间复杂度分析：算法1~2行时间复杂度为O(1)，3~4行时间复杂度为O(L)，5~9行时间复杂度为O(nL2)，10行时间复杂度为O(1)。故算法总的时间复杂度为O(nL2)。（3）设y[1:n]存储当找钱数为j的最优解时T[1:n]硬币分别找的个数。选择面值最大的T[i]，1≤i≤n，使C[n,j]=C[n,j-T[i]]+1，则子问题找钱数为j-T[i]的最优解y’[1:n]中，y’[i]+1后即为原问题的最优解y[1:n]。故问题的最优解可以通过子问题的最优解来达到，该问题具有贪心选择性。（假设T[1:n]的面值是递增的，并且C[n,L]是与排序后的T对应的结果）Input：T[1:n],C[1:L],mOutput：每个硬币对应的数目y[1:n]GET-CHANGE-NUMBER(T,C,m)1n←length(T),w←m2createarrayy[1:n]3fori←1ton4doy[i]←05whilew06dofori←nto17doifC[w]=C[w-T[i]]+18theny[i]←y[i]+19w←w-T[i]10break11returny时间复杂性分析：算法1~2行时间复杂度为O(1)，2~3行时间复杂度为O(n)，5~10行时间复杂度为O(m×n)，11行时间复杂度为O(1)。故算法总的时间复杂度为O(m×n)。2.设计一个动态规划算法从n个数构成的数列中找出最长单调递增子序列。答：（1）问题转化：设X[1:n]为n个数构成的序列，Y[1:n]为将X[1:n]中的数进行递增排序的结果。那么，原问题可以转化为求X和Y的最长公共子序列。设X中的最长单调递增子序列为xi,xj,…,xk,xm，那么在排序后的Y中，该子序列仍以这一顺序存在于Y中，显然该序列为X和Y的公共子序列。假设其不是X和Y的最长公共子序列，设其最长公共子序列为xi,xj,…,xp,…,xk,xm。由于Y为递增序列，因此有xixj…xp…xkxm。又因为xi,xj,…,xp,…,xk,xm是X的子序列，那么在X序列中，有一个更长的单调递增子序列xi,xj,…,xp,…,xk,xm。产生了矛盾，因此X的最长单调递增子序列即为X和Y的最长公共子序列。（2）优化子结构X和Y的LCS=(z1,z2,…,zk)的优化解结构为𝐿𝐶𝑆𝑋𝑌=𝐿𝐶𝑆𝑋𝑚−1𝑌𝑛−1+𝑥𝑚=𝑦𝑛𝑖𝑓𝑥𝑚=𝑦𝑛𝐿𝐶𝑆𝑋𝑌=𝐿𝐶𝑆𝑋𝑚−1𝑌𝑖𝑓𝑥𝑚≠𝑦𝑛，z𝑘≠𝑥𝑚𝐿𝐶𝑆𝑋𝑌=𝐿𝐶𝑆𝑋𝑌𝑛−1𝑖𝑓𝑥𝑚≠𝑦𝑛，z𝑘≠𝑦𝑚（3）递推方程C[i,j]=Xi和Yj的LCS的长度𝐶[i,j]=0𝑖𝑓𝑖=0或j=0𝐶[i,j]=C[i−1,j−1]+1𝑖𝑓𝑖,𝑗0且𝑥i=𝑦j𝐶[i,j]=max(C[i,j−1],C[i−1,j])𝑖𝑓𝑖,𝑗0且𝑥i=𝑦j（4）算法伪代码Input:数列X[1:n]Output：X的最长单调递增子序列LIS(X)1n←length(X)2createarrayY[1:n],C[n,n]andB[n,n]3Y←sort(X)4fori←1ton5doC[i,0]←0，C[0,j]←06fori←1ton7doforj←1ton8ifX[i]=Y[j]9thenC[i,j]←C[i-1,j-1]+1;B[i,j]←“↖”10elseifC[i-1,j]≥C[i,j-1]11thenC[i,j]←C[i-1,j];B[i,j]←“↑”12elseC[i,j]←C[i,j-1];B[i,j]←“←”13returnBandCPRINT-LIS(B,X,i,j)1ifi←0orj←02thenreturn3ifB[i,j]=“↖”4thenPRINT-LIS(B,X,i-1,j-1);printX[i]5elseifB[i,j]=“↑”6thenPRINT-LIS(B,X,i-1,j);7elsePRINT-LIS(B,X,i,j-1);时间复杂度分析：计算代价算法LIS(X)中，1~2行时间复杂度为O(1)，3行为排序算法，时间复杂度最低为O(nlogn)，4~5行时间复杂度为O(n)，6~12行时间复杂度为O(n2)，13行时间复杂度为O(1)；构造算法PRINT-LIS(B,X,i,j)中，时间复杂度为O(2n)。故算法总的时间复杂度为O(n2)。3.给定一个n×n的矩阵A，矩阵中的元素只取0或者1。设计一个动态规划算法，求解得到A中元素全是1的子方阵使其阶数达到最大值。答：（1）优化子结构：设n阶矩阵表示为A[1:n,1:n]，B[i,j]为A中前i行，前j列中1的个数。则1A[i][j]if10A[i][j]if0B-BBB1-j1,-i1-ji,j1,-iji,如果Bi,j-Bi-k,j-Bi,j-k+Bi-k,j-k=k2，那么在该位置存在一个k阶矩阵。（2）递推方程：设C[i,j]表示A中前i行前j列中元素全为1的子方阵的最大阶数。则递推方程为：C[i,j]=max{C[i−1,j],C[i,j−1],maxk{k≥max(C[i−1,j],C[i,j−1])|B[i,j]−B[i−k,j]−B[i,j−k]+B[i−k][j−k]=k×k}}（3）算法伪代码只要知道了Cn,n的值，就知道了最优解的阶数，为了知道这个最优解的具体信息，我们还需一个结构S，Si,j是Ci,j对应的方阵的右下角元素在A中对应的位置。因此，Sn,n就是最优解方阵右下角元素的位置，Cn,n是最优解的阶数。GET-MAX-MATRIX(A,n)1createarraysB[0:n][0:n],C[0:n][0:n],S[1:n][1:n]2fori←0ton3doB[i][0]←0;B[0][i]←0;C[i][0]←0;C[0][i]←0;4fori←0ton5doforj←0ton6doifA[i][j]=17thenB[i][j]←18elseB[i][j]←09B[i][j]←B[i][j]+B[i-1][j]+B[i][j-1]+B[i-1][j-1]10ifC[i-1][j]C[i][j-1]11thenC[i][j]←C[i-1][j]12S[i][j]←C[i-1][j]13elseC[i][j]←C[i][j-1]14S[i][j]←C[i][j-1]15fork←C[i][j]+1toi16doifi-k+11orj-k+1017thenbreak18ifB[i][j]-B[i-k+1][j]-B[i][j-k]+B[i-k][j-k]=k×k19thenC[i][j]←k20S[i][j](i,j)21elsebreak22returnSandC算法结束后，S[n][n]中有序实数对(i,j)为A中最大全1矩阵右下角元素的坐标。该矩阵为A[i-C[n][n]:i][j-C[n][n]:j]。时间复杂度分析：算法第1行时间复杂度为O(1)，2~3行时间复杂度为O(n)，4~22行时间复杂度为O(n3)，23行时间复杂度为O(1)。故算法总的时间复杂度为O(n3)。4.集合划分问题描述如下：输入：正整数集合S={a1,a2,a3,…,an};输出：是否存在A⊆S使得∑𝒂𝒊=∑𝒂𝒊𝒂𝒊∈𝑺−𝑨𝒂𝒊∈𝑨。试设计一个动态规划算法，求解集合划分问题。答：（1）问题转化：若集合划分A使得∑𝑎𝑖=∑𝑎𝑖𝑎𝑖∈𝑆−𝐴𝑎𝑖∈𝐴，则有∑𝑎𝑖=∑𝑎𝑖=12∑𝑎𝑖𝑎𝑖∈𝑆𝑎𝑖∈𝑆−𝐴𝑎𝑖∈𝐴。那么，该问题可转化为一个0-1背包问题。对于输入的正整数集合S={a1,a2,a3,…,an}。设X=(x1,x2,…,xn),xi∈{0,1},满足∑𝑥𝑖𝑎𝑖𝑛𝑖=1≤12∑𝑎𝑖𝑎𝑖∈𝑆,且∑𝑥𝑖𝑎𝑖𝑛𝑖=1最大。若此时∑𝑥𝑖𝑎𝑖𝑛𝑖=1=12∑𝑎𝑖𝑎𝑖∈𝑆,则存在这样的集合划分A，输出划分结果；否则不存在这样的集合A。（2）优化子结构：如果(y1,y2,…,yn)是0-1背包问题的有化解，则(y2,y3,…,yn)是如下子问题的优化解：∑𝑥𝑖𝑎𝑖𝑛𝑖=2≤12∑𝑎𝑖𝑎𝑖∈𝑆−𝑎1𝑦1；xi∈{0,1}，2≤i≤n。（3）递推方程：设背包容量为j，m(i,j)表示背包容量为j，可选物品为ai,ai+1,…,an时，问题的最优解的代价。因此递归方程为：m(i,j)=m(i+1,j)0≤jaim(i,j)=max(m(i+1,j),m(i+1,j−ai)+ai)j≥aim(n,j)=00≤janm(n,j)=anj≥an（4）算法伪代码：Input：正整数集合S={a1,a2,a3,…,an}Output：若存在A⊆S使得∑𝑎𝑖=∑𝑎𝑖𝑎𝑖∈𝑆−𝐴𝑎𝑖∈𝐴,则输出X;否则输出不存在。SET-PARTITION(S)1n←length(S),sum←02fori←1ton3dosum←sum+S[i]4half-sum←sum/25createarraym[1:n,0:half-sum]andX[1:n]6forj←0tomin(S[n]-1,half-sum)7dom[n,j]←08forj←S[n]tohalf-sum9dom[n,j]←S[n]10fori←n-1to211doforj←0tomin(S[i]-1,half-sum)12dom[i,j]←m[i+1,j]13forj←S[i]tohalf-sum14dom[i,j]←max{m[i+1,j],m[i+1,j-S[i]]+S[i]}15ifhalf-sumS[1]16thenm[1,half-sum]=m[2,half-sum]17elsem[1,half-sum]=max{m[2,half-sum],m[2,half-sum-S[1]]+S[1]}18ifm[1,sum/2]sum/219thenreturn“不存在”20w←half-sum21fori←1ton-122doifm[i,w]=m[i+1,w]23thenX[1]=024elseX[1]=125w←w-S[i]26ifw≥S[n]27thenX[n]=028elseX[n]=129returnX时间复杂度分析：第1行时间复杂度为O(1)，2~3行时间复杂度为O(n)，4~5行时间复杂度为O(1)，6~9行时间复杂度为O(n)，10~14行时间复杂度为O(n×half-sum)，15~20行时间复杂度为O(1)，21~26行时间复杂度为O(n)，27~29行时间复杂度为O(1)。综上所述，该算法的时间复杂度为O(n×half-sum)。5.设平面上有一个m×n的网格，将左下角的网格点标记为（0,0）而右上角的网格点标记为（m,n）。某人想从（0,0）出发沿网格线行进到达（m,n），但是在网格点（i,j）处他只能向上行进或者向右行进，向上行进的代价为𝒂𝒊𝒋(𝒂𝒎𝒋=+∞)，向右行进的代价是𝒃𝒊𝒋(𝒃𝒊𝒏=+∞)。试设计一个动态规划算法，在这个网格中为该旅行者寻找一条代价最小的旅行路线。你的答案应包括：（1）用简明的语言表述这个问题的优化子结构；（2）根据优化子结构写出代价方程；（3）根据代价方程写出动态规划算法（伪代码）并分析算法的时间复杂性；答：定义记号如下，c[i,j]表示从(0,0)点到(i,j)点路径的最小代价。（1）优化子结构：从(0,0)点走到