2013計算機算法設(shè)計與分析期終考試復(fù)習(xí)題

計算機算法設(shè)計與剖析復(fù)習(xí)題一、填空題1、一個算法復(fù)雜性的高低表此刻計算機運轉(zhuǎn)該算法所需的時間和儲存器資源上，所以算法的復(fù)雜性有時間復(fù)雜性和空間復(fù)雜性之分。2、出自于“均衡子問題”的思想，往常分治法在切割原問題，形成若干子問題時，這些子問題的規(guī)模都大概相同。3、使用二分搜尋算法在n個有序元素表中搜尋一個特定元素，在最正確狀況下，搜索的時間復(fù)雜性為

O（1），在最壞狀況下，搜尋的時間復(fù)雜性為

O（

logn

）。4、已知一個分治算法耗資的計算時間

T(n)

，T(n)

知足以下遞歸方程：

n

2O(1)T(n)

2T(n/2)

O(n)n

2解得此遞歸方可得

T(n)=O

（

）。

nlogn5、動向規(guī)劃算法有一個變形方法

備忘錄方法

。這類方法不一樣于動向規(guī)劃算法“自底向上”的填補方向，而是“自頂向下”的遞歸方向，為每個解過的子問題成立了備忘錄以備需要時查察，相同也可防止相同子問題的重復(fù)求解。遞歸的二分查找算法在

divide

階段所花的時間是

O(1)

，conquer

階段6．

所花的時間是

T(n/2)

，算法的時間復(fù)雜度是

O(logn)

。7．Prim算法利用貪婪策略求解最小生成樹問題，其時間復(fù)雜度是2O(n)。8．背包問題可用貪婪法，回溯法等策略求解。39．用動向規(guī)劃算法計算矩陣連乘問題的最優(yōu)值所花的時間是O(n)，子2問題空間大小是O(n)。10．圖的m著色問題可用回溯法求解，其解空間樹中葉子結(jié)點個數(shù)是nm，解空間樹中每個內(nèi)結(jié)點的孩子數(shù)是m。11．單源最短路徑問題可用貪婪法、分支限界等策略求解。12、一個算法的好壞能夠用（時間復(fù)雜度）與（空間復(fù)雜度）與來權(quán)衡。13、回溯法在問題的解空間中，按（深度優(yōu)先方式）從根結(jié)點出發(fā)搜尋解空間樹。14、直接或間接地調(diào)用自己的算法稱為（遞歸算法）。15、記號在算法復(fù)雜性的表示法中表示（漸進(jìn)確界或緊致界）。16、在分治法中，使子問題規(guī)模大概相等的做法是出自一種（均衡(banlancing)子問題）的思想。17、動向規(guī)劃算法合用于解（擁有某種最優(yōu)性質(zhì)）問題。18、貪婪算法做出的選擇不過（在某種意義上的局部）最精選擇。19、最優(yōu)子結(jié)構(gòu)性質(zhì)的含義是（問題的最優(yōu)解包含其子問題的最優(yōu)解）。20、回溯法按（深度優(yōu)先）策略從根結(jié)點出發(fā)搜尋解空間樹。21、拉斯維加斯算法找到的解必定是（正確解）。22、依照符號O的定義O(f)+O(g)等于O(max{f(n),g(n)})。23、二分搜尋技術(shù)是運用（分治）策略的典型例子。24、動向規(guī)劃算法中，往常不一樣子問題的個數(shù)隨問題規(guī)模呈（多項式）級增添。25、（最優(yōu)子結(jié)構(gòu)性質(zhì)）和（子問題重疊性質(zhì)）是采納動向規(guī)劃算法的兩個基本因素。26、（最優(yōu)子結(jié)構(gòu)性質(zhì)）和（貪婪選擇性質(zhì)）是貪婪算法的基本因素。27、（選擇能產(chǎn)生最優(yōu)解的貪婪準(zhǔn)則）是設(shè)計貪婪算法的核心問題。28、分支限界法常以（廣度優(yōu)先）或（以最小耗資(最大效益)優(yōu)先）的方式搜尋問題的解空間樹。29、貪婪選擇性質(zhì)是指所求問題的整體最優(yōu)解能夠經(jīng)過一系列（局部最優(yōu)）的選擇，即貪婪選擇達(dá)到。30、依照活結(jié)點表的組織方式的不一樣，分支限界法包含（行列式(FIFO)分支限界法）和（優(yōu)先行列式分支限界法）兩種形式。31、假如關(guān)于同一實例，蒙特卡洛算法不會給出兩個不一樣的正確解答，則稱該蒙特卡洛算法是（一致的）。32、哈夫曼編碼可利用（貪婪法）算法實現(xiàn)。33概率算法有數(shù)值概率算法，蒙特卡羅（MonteCarlo）算法，拉斯維加斯（LasVegas）算法和舍伍德（Sherwood）算法34以自頂向下的方式求解最優(yōu)解的有（貪婪算法）35、以下算法中往常以自頂向下的方式求解最優(yōu)解的是（

貪婪法）。

36、在對問題的解空間樹進(jìn)行搜尋的方法中

,一個活結(jié)點有多次時機成為活結(jié)點的是（

回溯法）

37、旅行售貨員問題不可以用（）解決

能夠用回溯法解決，分支限界法，

NP完整性理論與近似算法38、貪婪算法不可以解決（0-1背包問題N皇后問題）。能夠解決背包問題39、投點法是（概率算法）的一種。40、若線性規(guī)劃問題存在最優(yōu)解，它必定不在（可行域內(nèi)部）二、簡答題1、（8分）寫出以下復(fù)雜性函數(shù)的偏序關(guān)系（即依照漸進(jìn)階從低到高排序）：nn2n323lognn!nlognnn1032nnn10lognnlognn23n!n參照解答：2、（8分）此刻有8位運動員要進(jìn)行網(wǎng)球循環(huán)賽，要設(shè)計一個知足以下要求的競賽日程表：（1）每個選手一定與其余選手各賽一次；（2）每個選手一天只好賽一次；（3）循環(huán)賽一共進(jìn)行n–1天。請利用分治法的思想，給這8位運動員設(shè)計一個合理的競賽日程。參照解答：、（8分）某體育館有一羽毛球場出租，此刻總合有10位客戶申請租用此羽毛球場，每個客戶所租用的時間單元以下表所示，s(i)表示開始租用時刻，f(i)表示結(jié)束租用時刻，10個客戶的申請以下表所示：3153511886f(i)65498713121110同一時刻，該羽毛球場只好租借給一位客戶，請設(shè)計一個租用安排方案，在這10位客戶里面，使得體育館能盡可能知足多位客戶的需求，并算出針對上表的10個客戶申請，最多能夠安排幾位客戶申請。參照解答：將這10位客戶的申請依照結(jié)束時間f(i)遞加排序，以下表：i12345678910s(i(i)45678910111213⑴選擇申請1（1,4）⑵挨次檢查后續(xù)客戶申請，只需與已選擇的申請相容不矛盾，則選擇該申請。直到全部申請檢查完成。申請4（5,7）、申請8（8,11）、申請10（11,13）⑶最后，能夠知足：申請11,4）、申請4（5,7）、申請8（8,11）、申請10（11,13）共4個客戶申請。這已經(jīng)是能夠知足的最大客戶人數(shù)。4、（8

分）關(guān)于矩陣連乘所需最少量乘次數(shù)問題，其遞歸關(guān)系式為：

0i

jm[i,j]

min{m[i,k]

m[k

1,j]

ppp}i

j

i

1kj

i

kj此中

m[i

，j]

為計算矩陣連乘

Ai,Aj

所需的最少量乘次數(shù)，

p為矩陣

Ai

的行，i-1

為矩陣

Ai

的列?，F(xiàn)有四個矩陣，此中各矩陣維數(shù)分別為：pi4030305pppppppp01122334請依據(jù)以上的遞歸關(guān)系，計算出矩陣連乘積AAAA所需要的最少量乘次數(shù)。1234參照解答：m[1][1]m[2][4]ppp080005010510500014m[1][4]minm[1][2]m[3][4]ppp2000060005040536000024m[1][3]m[4][4]ppp2700005030534500034105005、（8分）有這樣一類特別0-1背包問題：可選物件重量越輕的物件價值越高。n=6，c=20，P=（4，8，15，1，6，3），W=（5，3，2，10，4，8）。此中n為物件個數(shù)，c為背包載重量，P表示物件的價值，W表示物件的重量。請問關(guān)于此0-1背包問題，應(yīng)怎樣選擇放進(jìn)去的物件，才能使到放進(jìn)背包的物件總價值最大，能獲取的最大總價值多少？參照解答：因為該0－1背包問題比較特別，恰巧重量越輕的物品價值越高，所以優(yōu)先取重量輕的物件放進(jìn)背包。最后能夠把重量分別為2，3，4，5

的三個物件放進(jìn)背包，獲取的價值和為

15+8+6+4=33

，為最大值。

6.請用英文寫出三種以上能求解

0-1

背包問題的設(shè)計算法策略。

參照解答：DynamicProgramming

Backtrack

Branch-and-Bound

（每答對一條給一分）7.請說明動向規(guī)劃方法為何需要最優(yōu)子結(jié)構(gòu)性質(zhì)。參照解答：最優(yōu)子結(jié)構(gòu)性質(zhì)是指大問題的最優(yōu)解包含子問題的最優(yōu)解。動向規(guī)劃方法是自底向上計算各個子問題的最優(yōu)解，即先計算子問題的最優(yōu)解，而后再利用子問題的最優(yōu)解結(jié)構(gòu)大問題的最優(yōu)解，所以需要最優(yōu)子結(jié)構(gòu)8.請說明：(1)優(yōu)先行列可用什么數(shù)據(jù)結(jié)構(gòu)實現(xiàn)？(2)優(yōu)先行列插入算法基本思想？(3)優(yōu)先行列插入算法時間復(fù)雜度？參照解答：（1）堆。(1分)（2）在小根堆中，將元素x插入到堆的末端，而后將元素x的重點字與其雙親的重點字比較，若元素x的重點字小于其雙親的重點字，則將元素x與其雙親互換，而后再將元素x與其新雙親的重點字對比，直到元素x的重點字大于雙親的關(guān)鍵字，或元素x到根為止。(4分)（3）O(logn)（1分）9..設(shè)計動向規(guī)劃算法的主要步驟是怎么的？請簡述。參照解答：（1）找出最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特色。(6分)（2）遞歸地定義最優(yōu)值。（3）以自底向上的方式計算出最優(yōu)值。（4）依據(jù)計算最優(yōu)值時獲取的信息，結(jié)構(gòu)最優(yōu)解。10.分治法所能解決的問題一般擁有哪幾個特色？請簡述。參照解答：（1）該問題的規(guī)模減小到必定的程度就能夠簡單地解決；(6分)（2）該問題能夠分解為若干個規(guī)模較小的相同問題，即該問題擁有最優(yōu)子結(jié)構(gòu)性質(zhì);（3）利用該問題分解出的子問題的解能夠合并為該問題的解；（4）原問題所分解出的各個子問題是互相獨立的，即子問題之間不包含公共的子問題。11.分支限界法的搜尋策略是什么？參照解答：在擴展結(jié)點處，先生成其全部的兒子結(jié)點（分支），而后再從目前的活結(jié)點表中選擇下一個擴展結(jié)點。為了有效地選擇下一擴展結(jié)點，加快搜尋的進(jìn)度，在每一個活結(jié)點處，計算一個函數(shù)值（限界），并依據(jù)函數(shù)值，從目前活結(jié)點表中選擇一個最有益的結(jié)點作為擴展結(jié)點，使搜尋朝著解空間上有最優(yōu)解的分支推動，以便趕快地找出一個最優(yōu)解。(6分)12算法的要特征是什么？參照解答：確立性、可實現(xiàn)性、輸入、輸出、有窮性13算法剖析的目的是什么？參照解答：剖析算法占用計算機資源的狀況，對算法做出比較和評論，設(shè)計出額更好的算法。14算法的時間復(fù)雜性與問題的什么因素有關(guān)？參照解答：算法的時間復(fù)雜性與問題的規(guī)模有關(guān)，是問題大小n的函數(shù)。15算法的漸進(jìn)時間復(fù)雜性的含義？參照解答：當(dāng)問題的規(guī)模n趨勢無量大時，影響算法效率的重要因素是T(n)的數(shù)目級，而其余因素僅是使時間復(fù)雜度相差常數(shù)倍，所以能夠用T(n)的數(shù)目級(階)評論算法。時間復(fù)雜度T(n)的數(shù)目級(階)稱為漸進(jìn)時間復(fù)雜性。16最壞狀況下的時間復(fù)雜性和均勻時間復(fù)雜性有什么不一樣？參照解答：最壞狀況下的時間復(fù)雜性和均勻時間復(fù)雜性觀察的是n固準(zhǔn)時，不一樣輸入實例下的算法所耗時間。最壞狀況下的時間復(fù)雜性取的輸入實例中最大的時間復(fù)雜度：W(n)=max{T(n，},I∈Dn均勻時間復(fù)雜性是全部輸入實例的辦理時間與各自概率的乘積和：A(n)=∑P(I)T(n，I)I∈Dn17簡述二分檢索（折半查找）算法的基本過程。參照解答：設(shè)輸入是一個按非降序次擺列的元素表A[i：j]和x，選用A[(i+j)/2]與x比較，假如A[(i+j)/2]=x，則返回(i+j)/2，假如A[(i+j)/2]<x，則A[i：(i+j)/2-1]找x，不然在A[(i+j)/2+1：j]找x。上述過程被頻頻遞歸調(diào)用。18背包問題的目標(biāo)函數(shù)和貪婪算法最優(yōu)化量度相同嗎？參照解答：不相同。目標(biāo)函數(shù)：獲取最大收益。最優(yōu)量度：最大收益/重量比。19采納回溯法求解的問題，其解怎樣表示？有什么規(guī)定？參照解答：問題的解能夠表示為n元組：（x,x,,,x），x∈S,S為有窮會合，12niiix∈S,（x,x,,,x）具備齊備性，即（x,x,,,x）是合理的，則（x,x,,,x）ii12n12n12i(i<n)必定合理。20回溯法的搜尋特色是什么？參照解答：在解空間樹上跳躍式地深度優(yōu)先搜尋，即用判斷函數(shù)觀察x[k]的取值，假如x[k]是合理的就搜尋x[k]為根節(jié)點的子樹，假如x[k]取完了全部的值，便回溯到x[k-1]。21n皇后問題回溯算法的鑒別函數(shù)place的基本流程是什么？參照解答：將第K行的皇后分別與前k-1行的皇后比較，看是否與它們相容，假如不相容就返回false，測試完成則返回true。22為何用分治法設(shè)計的算法一般有遞歸調(diào)用？參照解答：子問題的規(guī)模還很大時，一定持續(xù)使用分治法，頻頻分治，必定要用到遞歸.23為何要剖析最壞狀況下的算法時間復(fù)雜性？參照解答：最壞狀況下的時間復(fù)雜性決定算法的好壞，而且最壞狀況下的時間復(fù)雜性較均勻時間復(fù)雜性游可操作性。24簡述漸進(jìn)時間復(fù)雜性上界的定義。參照解答：T(n)是某算法的時間復(fù)雜性函數(shù)，f(n)是一簡單函數(shù)，存在正整數(shù)No和C，n〉No，有T(n)<f(n)，這類關(guān)系記作T(n)=O(f(n))。25二分檢索算法最多的比較次數(shù)？參照解答：二分檢索算法的最多的比較次數(shù)為logn。26迅速排序算法最壞狀況下需要多少次比較運算？2參照解答：最壞狀況下迅速排序退化成冒泡排序，需要比較n次。27貪婪算法的基本思想？參照解答：是一種依照最優(yōu)化量度挨次選擇輸入的分級辦理方法?；舅悸肥牵旱谝灰罁?jù)題意，選用一種量度標(biāo)準(zhǔn)；而后按這類量度標(biāo)準(zhǔn)對這n個輸入排序，挨次選擇輸入量加入部分解中。假如目前這個輸入量的加入，不知足拘束條件，則不把此輸入加到這部分解中28回溯法的解（x,x,,,x）的隱拘束一般指什么？12n參照解答：回溯法的解（x,x,,,x）的隱拘束一般指個元素之間應(yīng)知足的某12n種關(guān)系。29論述合并排序的分治思路。參照解答：講數(shù)組一分為二，分別對每個會合獨自排序，而后將已排序的兩個序列合并成一個含n個元素的分好類的序列。假如切割后子問題還很大，則持續(xù)分治，直到一個元素。30迅速排序的基本思想是什么。參照解答：迅速排序的基本思想是在待排序的N個記錄中隨意取一個記錄，把該記錄放在最后地點后，數(shù)據(jù)序列被此記錄分紅兩部分。全部重點字比該記錄重點字小的放在前一部分，全部比它大的擱置在后一部分，并把該記錄排在這兩部分的中間，這個過程稱作一次迅速排序。以后重復(fù)上述過程，直到每一部分內(nèi)只有一個記錄為止。31什么是直接遞歸和間接遞歸？除去遞歸一般要用到什么數(shù)據(jù)結(jié)構(gòu)？參照解答：在定義一個過程或許函數(shù)的時候又出現(xiàn)了調(diào)用本過程或許函數(shù)的成分，既調(diào)用它自己自己，這稱為直接遞歸。假如過程或許函數(shù)P調(diào)用過程或許函數(shù)Q，Q又調(diào)用P，這個稱為間接遞歸。除去遞歸一般要用到棧這類數(shù)據(jù)結(jié)構(gòu)。32什么是哈密頓環(huán)問題？參照解答：哈密頓環(huán)是指一條沿著圖G的N條邊環(huán)行的路徑，它的接見每個節(jié)點一次而且返回它的開始地點。33用回溯法求解哈密頓環(huán)，怎樣定義判斷函數(shù)？

參照解答：目前選擇的節(jié)點

X[k]是從未到過的節(jié)點

,即

X[k]

≠X[i](i=1,2,,,k

-1)

，且

C(X[k-1],X[k])

≠∞，假如k=-1，則

C(X[k],X[1])

≠∞。

34

請寫出

prim

算法的基本思想。

參照解答：思路是：最先生成樹

T為空，挨次向內(nèi)加入與樹有最小毗鄰邊的

n-1

條邊。辦理過程：第一加入最小代價的一條邊到T，依據(jù)各節(jié)點到T的毗鄰邊排序，選擇最小邊加入，新邊加入后，改正因為新邊所改變的毗鄰邊排序，再選擇下一條邊加入，直至加入n-1條邊。三、算法設(shè)計題【最長上漲子序列問題】（8分）——提示：本題可采納動向規(guī)劃算法實現(xiàn)對于給定的一個序列，。我們能夠獲取一些遞加(a,a,,a)1N100012N上漲的子序列比方，關(guān)于序列

(1,7,

。這里，

(a,a,

i

N1

i

i

,a)

i1i2K12iK

3,5,9,4,8)

，有它的一些上漲子序列，如

(1,7),(3,4,8)

等等。這些子

序列中最長的長度是

4，比方子序列

(1,3,5,8)

。你的任務(wù)：就是關(guān)于給定的序列，求出最長上漲子序列的長度。要求寫出你設(shè)計的算法思想及遞推函數(shù)的公式表達(dá)。.參照解答：設(shè)表示：從左向右掃描過來直到以元素結(jié)尾的序列，獲取的f(i)a[i]最長上漲子序列的長度，且子序列包含元素（）。1ina[i]1i1f(i)max{f(j)1:當(dāng)a[i]a[j];1ji}i11i1;j(1ji),都有a[i]a[j]即，是從，,,到中找最大的一個值，再加1。或許f(i)f(1)f(2)f(i1)就是1。主假如看a[i]這個元素可否加入到以前已經(jīng)獲取的最長上漲子序列，假如能加入，是以前已獲取的最長上漲子序列長度加一；假如不可以加入，就取這最后一個元素作為一個獨自子序列，長度為1。最后，所要求的整個序列的最長公共子序列長度為

max{f(i):1<=i<=n}

比如，對于序列：4263152

i1234567

array4263152f(i)1122132

評分準(zhǔn)則：答到使用動向規(guī)劃算法，而且推導(dǎo)出動向規(guī)劃算法的遞推函數(shù)公式表達(dá)，1)界限設(shè)定清楚，本題即可得滿分；（閱卷時認(rèn)真看遞推公式表達(dá)，公式表達(dá)含義正確即可，因其表達(dá)形式可能不獨一）說明使用動向規(guī)劃算法，但對遞推函數(shù)表達(dá)錯誤或含糊，扣2分以上；2)其余狀況酌情考慮。3)2．（10分）對以下圖所示的連通網(wǎng)絡(luò)G，用克魯斯卡爾(Kruskal)算法求G的最小生成樹T,請寫出在算法履行過程中，挨次加入T的邊集TE中的邊。說明該算法的貪婪策略和算法的基本思想，并簡要剖析算法的時間復(fù)雜度。18217211911963261564517參照解答TE={(3,4),(2,3),(1,5),（4,6）（4,5）}（5分）貪婪策略是每次都在連結(jié)兩個不一樣連通重量的邊中選權(quán)值最小的邊?；舅枷耄旱谝粚D中全部極點都放到生成樹中，而后每次都在連結(jié)兩個不一樣連通重量的邊中選權(quán)值最小的邊，將其放入生成樹中，直到生成樹中有n-1條邊。（4分）時間復(fù)雜度為：O(eloge)（1分）3.（15分）考慮n=3的批辦理作業(yè)調(diào)動實例：t機器1機器2ji作業(yè)1110作業(yè)231作業(yè)321i此中t是作業(yè)J需要在機器j上辦理的時間。關(guān)于給定的3個作業(yè)，擬訂ji一個最正確作業(yè)調(diào)動方案，使其達(dá)成時間和達(dá)到最小。要求：（1）畫出該問題的解空間樹；（5分）（2）寫出該問題的剪枝策略(即限界條件),要求只保存第一個最優(yōu)解;(2分)（3）按優(yōu)先行列式分支限界法搜尋解空間樹，并用剪枝策略對解空間樹中該剪枝的地點打；最優(yōu)解及最優(yōu)值。

（3

（5分）（4）給出分）參照解答（1）5分V0132114323132118101692323323112333025363626※fbestf（2）若目前代價>=目前最優(yōu)解代價，則剪枝。2分（3）見（1）中所畫的圖。5分（4）最優(yōu)解為{3，1，2}，最優(yōu)值為25。3分4.【Gray碼結(jié)構(gòu)問題】（8

分）——提示：本題可采納分治遞歸算法實現(xiàn)

n問題描繪：“格雷碼”是一個長度為的序列，知足：

2（a）每個元素都是長度為

n比特的串（b）序列中無相同元素（c）連續(xù)的兩個元素恰巧只有1個比特不一樣比如：n=2時，格雷碼為{00，01，11，10}。Gray碼是一種編碼，這類編碼能夠防止在讀取時，因各數(shù)據(jù)位時序上的差別造成的誤讀。格雷碼在工程上有寬泛應(yīng)用。但格雷碼不便于運算，請你設(shè)計一種結(jié)構(gòu)方法，輸入長度序列n，輸出格雷碼（你只需做出一種結(jié)構(gòu)方案即可，格雷碼其實不獨一）。參照解答：本題可用分治法解決。當(dāng)n＝1時，輸出格雷碼{0,1}nn22當(dāng)n>1時，格雷碼的長度為，即共有個碼序列。此時，將問題一分為二，即上半部分和下半部分。上半部分最高位設(shè)為0，下半部分最高位設(shè)為1。剩下n-1位的格雷碼的結(jié)構(gòu)采納遞歸的思路。評分準(zhǔn)則：答到使用分治算法，而且推導(dǎo)出分治算法的過程，界限設(shè)定清楚（即當(dāng)1)僅輸出1位的格雷碼如何辦理），本題即可得滿分；說明使用分治算法，但漏界限條件，扣2分以上；2)其余狀況酌情考慮。.（13分）給定帶權(quán)有向圖（以以下圖所示）G=(V,E)，其中每條邊的權(quán)是非負(fù)5實數(shù)。此外，還給定V中的一個極點，稱為源。此刻要計算從源到全部其余各極點的最短路長度。這里路的長度是指路上各邊權(quán)之和?，F(xiàn)采納Dijkstra算法計算從源極點1到其余極點間最短路徑。請將此過程填入下表中。Sudist[2]dist[3]dist[4]dist[5]迭代{1}初始1234參照解答：（13分）Sudist[2]dist[3]dist[4]dist[5]迭代{1}-1030100初始{1，2}21060301001{1，2，4}4105030902{1，2，4，3}3105030603{1，2，3，4，5}51050306046.（13分）有0-1背包問題以下：n=6，c=20，P=（4，8，15，1，6，3），W=（5，3，2，10，4，8）。此中n為物件個數(shù)，c為背包載重量，P表示物件的價值，W表示物件的重量。請問關(guān)于此0-1背包問題，應(yīng)怎樣選擇放進(jìn)去的物件，才能使到放進(jìn)背包的物件總價值最大。P=(15，8，6，4，3，1)W=(2，3，4，5，8，10)，單位重量物件價值（7.5，2.67，1.5,0.8,0.375,0.1）參照解答：（13分）可知跟著物件的重量增添，物件的價值減少；