2.某公司有資金4百萬元向a,b和c3個專案追加投資，各個專案可以有不同的投資額（百萬元計），相應的效益如表所示。問怎樣分配資金，使總效益值最大？##
表8－47
解：設s1－a,b,c專案的總投資額，s2－b、c專案的總投資額
s3－c專案的投資額；
xk－k專案的投資額；
（x1－a專案的投資額，x2－b專案的投資額，x3－c專案的投資額）
wk（sk,xk）－對k專案投資xk後的收益：wk（sk,xk）＝wk (xk)
tk (sk,xk)－sk+1=sk-xk
fk (sk)－當k至第3專案允許的投資額為sk時所能獲得的最大收益。
為獲得最大利潤，必須將4百萬全部投資，假設有4階段存在，有s4＝0，建立遞迴方程
f4 (sk)=0
fk (sk)=max
x3∈d3(s3)
s4=s3-x3
第二步：
k=2f2 (s2)=max
x2∈d2(s2)
s3=s2-x2
w2 (x2)+f3 (s2-x2)
第三步：
k=1f1 (s1) =max
x1∈d1(s1)
s2= s1- x1
w1 (x1)+ f2 (s1- x1)
s1=4 → s2=1s3=1
x1*=3 x2*=0x3*=1
a投資3百萬， b不投資 c投資1百萬。
總收益 164百萬元。
3.（最優分配問題）有乙個儀表公司打算向它的3個營業區設立6家銷售店。每個營業區至少設一家，所獲利潤如表。問設立的6家銷售店數應如何分配，可使總利潤最大？
解：sk——對k#,…,3#營業區允許設立的銷售店數
xk——對k#營業區設立的銷售店數
wk (sk,xk)——對k#營業區設立xk銷售店後的利潤：
wk (sk,,xk)= wk (xk)
tk (sk, xk)——sk +1= sk - xk
fk (sk)——當第k至第3個營業區允許設立的銷售店數為sk時所能獲得的最大利潤
遞迴方程：
f4(s4)=0
fk (sk)=max ｛wk (xk)+ fk+1(sk+1)｝, k=3,2,1
xk∈dk(sk)
k=3時，有方程
f4 (s4)=0
f3(s3)= max ｛w3(x3)+ f4(s4) ｝
x3∈d3(s3)
s3=s2—x2
k=2,有方程
f2(s2)= max ｛w2(x2)+ f3(s3) ｝
x2∈d2(s2)
s3=s2—x2
k=1,有方程
f1(s1)= max ｛w1(x1)+ f2(s2) ｝
x1∈d1(s1)
s2=s1—x1
s1=6 → s2=3 → s3=2
x1*=3 x2*=1 x3*=2
分別a1、a2、a3營業區設立3家、1家、2家銷售店，最大利潤為770
4．用動態規劃方法求解下列模型：
maxf=10x1+4x2+5x3
s.t. 3x1+5 x2+4 x3≤15
0≤x1≤2 0≤x2≤2 x3≥0 ，xj為整數 j=1,2,3
解：收費c1=10 c2=4 c3=5
x1為貨物1的裝載件數
x2為貨物2的裝載件數
x3為貨物3的裝載件數
分3階段
s1為貨物1、2、3允許的裝載重量（3x1+5 x2+4 x3的允許值）
s2為貨物2、3允許裝載的重量（5 x2+4 x3的允許值）
s3 為貨物3允許裝載的重量（4 x3的允許值）
第一步：k=3
f4(s4)=0
f3(s3)= max
s4= s3 -4 x3
第二步：k=2
f2(s2)= max
s3= s2 -5 x2
劃分點：
第三步：k=1
f1(s3)= max
s2= s1-3 x1
10x1+ f2(s1-3 x1)
順序追蹤：最優策略為
s1=15s2=9s3=9
x1*=2x2*=0x3*=2
最優裝載方案為：貨物1裝2件；貨物2不裝；貨物3裝2件
裝載收費為30元
5.用動態規劃方法解下列0—1揹包問題：
max f =12x1+12x2+9x3+16x4+30x5；
s.t. 3x1+4x2+3x3+4x4+6x5≤12;
xj=0,1, j=1,……，5
解： 本問題分為5個階段。令
sk——akxk+…+a4x4的允許值
xk——第k階段xk取值，xk=0，1
wk(sk, xk)——xk產生的價值：wk(sk, xk)=c kxk
tk(sk, xk)——sk+1=sk- akxk
fk(sk)——在akxk+…+ a4x4≤sk的條件下，c kxk+…+c 4x4能取得的最大值。
遞迴方程為
k=5f5(s5)=max
k=4k=3k=2
5動態規劃演算法習題答案
1 最大子段和問題 給定整數序列，求該序列形如的子段和的最大值 1 已知乙個簡單演算法如下 int maxsum int n,int a,int best i,int bestj return sum 試分析該演算法的時間複雜性。2 試用分治演算法解最大子段和問題，並分析演算法的時間複雜性。3 試說...
動態規劃練習題及解答
題1 多公尺諾骨牌 domino 問題描述 有一種多公尺諾骨牌是平面的，其正面被分成上下兩部分，每一部分的表面或者為空，或者被標上1至6個點。現有一行排列在桌面上 頂行骨牌的點數之和為6 1 1 1 9 底行骨牌點數之和為1 5 3 2 11。頂行和底行的差值是2。這個差值是兩行點數之和的差的絕對值...
動態規劃練習
任務 請寫乙個程式 在文字檔案tan.in中讀入路程的總長度 旅館的數目和對旅館的描述 找出兩個旅行的方案 乙個最便宜的方案 就是付出的宿費最少的方案 如果有多個方案，選擇在旅館中度夜的次數最少的方案 乙個最短的方案 就是在旅館中度夜的次數最少的方案 如果有多個方案，選擇花費最少的方案 把結果，就是...