0-1背包問(wèn)題:現(xiàn)有一背包容量c=5,n=4。4個(gè)物品分別為:
(Wi,Vi)∣(1,3),(3,6),(4,9),(2,7)。如下m表中m[i][j]是前i個(gè)物品裝背包容量為j時(shí)的最優(yōu)值。
其中第四行的數(shù)據(jù)沒(méi)有填寫(xiě),分析問(wèn)題,將第四行的數(shù)據(jù)從如下選項(xiàng)中找出()。
A.0,3,3,6,8,15
B.0,3,7,7,10,13
C.0,3,7,10,10,13
D.0,3,7,10,13,15
您可能感興趣的試卷
你可能感興趣的試題
?凸多邊形的三角剖分問(wèn)題。用動(dòng)態(tài)規(guī)劃算法求解最優(yōu)三角剖分,首先要分析最優(yōu)解的結(jié)構(gòu),也就是將問(wèn)題分解為子問(wèn)題,并具有最優(yōu)子結(jié)構(gòu)性質(zhì)。下圖是一凸6邊形(ABCDEF)的二種不同劃分為子問(wèn)題的方法,哪種是正確的將問(wèn)題劃分為子問(wèn)題的方案?正確的劃分方案共有幾種不同方式?()
A.右圖正確,4種
B.右圖正確,9種
C.左圖正確,4種
D.左圖正確,9種
矩陣連乘問(wèn)題:下圖是動(dòng)態(tài)規(guī)劃算法計(jì)算6個(gè)矩陣A1A2A3A4A5A6連乘所生成的信息表
(a)表描述了計(jì)算順序
(b)表是m[i][j]的最優(yōu)值表
(c)表是輔助信息表(斷開(kāi)位置)
分析表格,給出A2A3A4A5A6五個(gè)矩陣連乘所需要的最少數(shù)乘次數(shù),并用加括號(hào)的方法表示出其乘法順序()。
A.15125,(A2A3)((A4A5)A6)
B.10500,(A2(A3A4))(A5A6)
C.15125,(A2(A3A4))(A5A6)
D.10500,(A2A3)((A4A5)A6)
動(dòng)態(tài)規(guī)劃解題的步驟分為四步:
(1)分析最優(yōu)解的結(jié)構(gòu)
(2)建立遞歸關(guān)系
(3)計(jì)算最優(yōu)值
(4)構(gòu)造最優(yōu)解
關(guān)于這四個(gè)步驟的內(nèi)容描述不正確的是哪個(gè)?()
A.計(jì)算最優(yōu)值:以自頂往下的方法計(jì)算問(wèn)題的最優(yōu)值,也就是先求解規(guī)模較大的問(wèn)題的最優(yōu)值
B.構(gòu)造最優(yōu)解:根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息構(gòu)造出問(wèn)題的最優(yōu)解,通常是用遞歸算法完成最優(yōu)解的構(gòu)造
C.建立遞歸關(guān)系:建立關(guān)于問(wèn)題最優(yōu)值的遞歸定義,即問(wèn)題的最優(yōu)值通過(guò)子問(wèn)題的最優(yōu)值合并得到
D.分析最優(yōu)解的結(jié)構(gòu):一個(gè)一般化問(wèn)題可以分解為幾個(gè)性質(zhì)相同的子問(wèn)題,并且問(wèn)題的最優(yōu)解可以通過(guò)子問(wèn)題的最優(yōu)解合并得到,也就是要滿足最優(yōu)子結(jié)構(gòu)性質(zhì)
A.O(n)
B.O(nlogn)
C.O(logn)
D.O(n2)
A.結(jié)構(gòu)清晰
B.容易用數(shù)學(xué)歸納法證明算法的正確性
C.遞歸算法耗費(fèi)的時(shí)間和占用的內(nèi)存空間要比解決同一問(wèn)題的非遞歸算法要少
D.可讀性強(qiáng)
最新試題
已知f(1)=1,f(n)=f(n-1)+n,那么f(50)的作用是()。
使用窮舉法求解最長(zhǎng)遞增子序列的時(shí)間復(fù)雜度為()。
應(yīng)用分支限界法的三個(gè)關(guān)鍵問(wèn)題包括()。
在隊(duì)列式分支限界法解決裝載問(wèn)題時(shí),為什么在其改進(jìn)算法中,每次進(jìn)入左分支都要檢查更新bestw,而不是等搜索到達(dá)葉子結(jié)點(diǎn)時(shí)才去更新bestw,其目的是什么?()
序列(1,7,3,4,9,2,3)的最長(zhǎng)遞增子序列的長(zhǎng)度為()。
在解決活動(dòng)安排問(wèn)題時(shí)應(yīng)首先對(duì)活動(dòng)進(jìn)行排序,排序的依據(jù)是()。
下列關(guān)于效率的說(shuō)法正確的是()。
?在分治法中講到快速排序,如果每次使用partion函數(shù)導(dǎo)致分組出現(xiàn)嚴(yán)重不平衡情況下,算法效率不高,最壞情況下的時(shí)間復(fù)雜度為O(n2),通過(guò)改造partition函數(shù),也就是每次隨機(jī)選擇一個(gè)元素作為劃分基準(zhǔn),這樣會(huì)很好地改善算法的性能,這種算法思想是()。
舍伍德算法思想是通過(guò)引入隨機(jī)化策略將確定性算法改造為隨機(jī)算法,打破原來(lái)確定性算法在某些實(shí)例情況下,其時(shí)間復(fù)雜性必然遠(yuǎn)高于平均時(shí)間復(fù)雜性的規(guī)律。下面哪些算法可以應(yīng)用舍伍德算法思想?()
輸入數(shù)組(-1,0,1,-2,3),它的最大子段和是()。