1．最大子段和問題：給定整數序列，求該序列形如的子段和的最大值：
1) 已知乙個簡單演算法如下：
int maxsum(int n,int a,int& best i,int& bestj)
} }
return sum;
}試分析該演算法的時間複雜性。
2) 試用分治演算法解最大子段和問題，並分析演算法的時間複雜性。
3) 試說明最大子段和問題具有最優子結構性質，並設計乙個動態規劃演算法解最大子段和問題。分析演算法的時間複雜度。
（提示：令）
解：1）分析按照第一章，列出步數統計表，計算可得
2）分治演算法：將所給的序列a[1:n]分為兩段a [1:n/2]、a[n/2+1:n]，分別求出這兩段的最大子段和，則a[1:n]的最大子段和有三種可能：
①a[1:n]的最大子段和與a[1:n/2]的最大子段和相同；
②a[1:n]的最大子段和與a[n/2+1:n]的最大子段和相同；
③a[1:n]的最大子段和為兩部分的字段和組成，即；
intmaxsubsum ( int *a, int left , int right)
int s2 =0;
int right_sum =0;
for ( int i = center +1; i <= right ; i++)
sum = s1 + s2;
if ( sum < leftsum)
sum = leftsum;
if ( sum < rightsum)
sum = rightsum;
} return sum;
}int maxsum2 (int n) 該演算法所需的計算時間t(n)滿足典型的分治演算法遞迴分式
t(n)=2t(n/2)+o(n)，分治演算法的時間複雜度為o(nlogn)
3）設,則最大子段和為
最大子段和實際就是.
要說明最大子段和具有最優子結構性質，只要找到其前後步驟的迭代關係即可。
若,；若，。因此，計算的動態規劃的公式為：
intmaxsum (int* a，int n )
if( b > sum)
sum = b;
j=i；
end}return sum;
}自行推導，答案：時間複雜度為o（n）。
2. 動態規劃演算法的時間複雜度為o（n）（雙機排程問題）用兩台處理機a和b處理個作業。設第個作業交給機器a處理時所需要的時間是，若由機器b來處理，則所需要的時間是。
現在要求每個作業只能由一台機器處理，每台機器都不能同時處理兩個作業。設計乙個動態規劃演算法，使得這兩台機器處理完這個作業的時間最短（從任何一台機器開工到最後一台機器停工的總的時間）。以下面的例子說明你的演算法：
解：（思路一）在完成前k個作業時，設機器a工作了x時間，則機器b此時最小的工作時間是x的乙個函式。
設f[k][x]表示完成前k個作業時，機器b最小的工作時間，則
其中對應第k個作業由機器b來處理（完成k-1個作業時機器a工作時間仍是x，則b在k-1階段用時為）；而對應第k個作業由機器a處理（完成k-1個作業，機器a工作時間是x-a[k]，而b完成k階段與完成k-1階段用時相同為）。
則完成前k個作業所需的時間為
1）當處理第乙個作業時，a[1]=2,b[1]=3;
機器a所花費時間的所有可能值範圍：0 x a[0].
x<0時，設f[0][x]= ∞，則max(x, ∞)= ∞；
0x<2時，f[1][x]=3，則max(0,3)=3，
x2時， f[1][x]= 0，則max(2,0)=2；
2）處理第二個作業時：x的取值範圍是：0 <= x <= (a[0] + a[1])，
當x<0時，記f[2][x] = ∞；以此類推下去
（思路二）假定個作業的集合為。
設為的子集，若安排中的作業在機器a上處理，其餘作業在機器b上處理，此時所用時間為，
則雙機處理作業問題相當於確定的子集，使得安排是最省時的。即轉化為求使得。若記，則有如下遞推關係：
（思路三）
此問題等價於求（x1,……xn），使得它是下面的問題最優解。
min max xi=0或1，i=1~n
基於動態規劃演算法的思想，對每個任務i，依次計算集合s(i)。其中每個集合中元素都是乙個3元組（f1,f2,x）。這個3元組的每個分量定義為
f1:處理機a的完成時間
f2：處理機b的完成時間
x：任務分配變數。當xi=1時表示將任務i分配給處理機a，當xi=0時表示分配給處理機b。
初始時，s(0)=
令f=按處理時間少的原則來分配任務的方案所需的完成時間。
例如，當（a1，a2,a3,a4,a5,a6）=(2,5,7,10,5,2),(b1,b2,b3,b4,b5,b6)=(3,8,4,11,3,4)時，按處理時間少的原則分配任務的方案為（x1,x2,x3,x4,x5,x6）=（1,1,0,1,0,1）
因此，f=max=19。
然後，依次考慮任務i，i=1~n。在分配任務i時，只有2種情形，xi=1或xi=0。此時，令s(i)=u在做上述集合並集的計算時，遵循下面的原則：
①當（a,b,c）,(d,e,f)s(i)且a=d,b<=e時，僅保留（a,b,c）；
僅當max<=f時，(a,b,c)s(i)
最後在s(n)中找出使max達到最小的元素，相應的x即為所求的最優解，其最優值為max。
當（a1，a2,a3,a4,a5,a6）=(2,5,7,10,5,2),(b1,b2,b3,b4,b5,b6)=(3,8,4,11,3,4)時, 按處理時間少的原則分配任務的方案為（x1,x2,x3,x4,x5,x6）=（1,1,0,1,0,1）
因此，f=max=19。
s(0)=;
s(1)=
s(2)=
s(3)=
s(4)=
s(5)=
s(6)=
max(f1,f2)最小的元組為(14,15,102), (14,15,82), (15,14,20)
所以，完成所有作業最短時間是15，安排有三種：
（1,1,0,0,1,1），（1,0,0,1,0,1）,(0,1,0,1,0,0)
3．考慮下面特殊的整數線性規劃問題
試設計乙個解此問題的動態規劃演算法，並分析演算法的時間複雜度。
解：方法1.
設令，則上述規劃問題轉化為：
，其中，
把看作價值，看作重量，看作揹包容量。
轉化為0/1揹包問題，所以可以0/1揹包問題的動態規劃演算法來求解。由於n件物品的0/1揹包的時間複雜性是o（2n），則此時為o（4n）。
方法2.
可以看成是另一種揹包問題。即b為揹包容量，為揹包中可以裝0，1，或者2件物品，對應的價值為，求在容量b 一定的前提下，揹包所容納的物品的最大價值。也就是引數完全相同的兩個0-1揹包問題，它們同時制約於揹包容量為c這個條件。
在設計演算法時可以優先考慮，也就是先判斷揹包剩下的容量能不能放進去，若可以再判斷能否使，若可以則就再放入乙個，這樣就間接滿足了的條件。
動態規劃演算法
首先，我們來觀察一下這個演算法。在求從b1到e的最短距離的時候，先求出從c2到e的最短距離 而在求從b2到e的最短距離的時候，又求了一遍從c2到e的最短距離。也就是說，從c2到e的最短距離我們求了兩遍。同樣可以發現，在求從c1 c2到e的最短距離的過程中，從d1到e的最短距離也被求了兩遍。而在整個程...
揹包問題的動態規劃演算法
1.u1 c 2.m n 1時，fm u 恒為0 3.u 0時，fm u 為0 狀態轉移方程為u k 1 uk xk wk。動態規劃基本方程為 wm u時，fm u f m 1 u 否則fm u 為f m 1 u與f m 1 u wm pm中的較大者。定義 n 1 c矩陣f，其m行u列處為fm u ...
實驗二動態規劃演算法的應用
一 實驗目的 2 二 實驗內容 2 2.1數塔問題 2 2.2 最長單調遞增子串行問題 2 三 演算法設計 2 3.1 數塔問題 2 3.1.1演算法描述 2 3.1.2 函式設計 3 3.2 最長單調遞增子串行問題 3 3.1.1演算法描述 3 3.1.2 函式設計 3 四.程式除錯及執行結果分析...