算法設(shè)計與分析課程設(shè)計報告(已修改)
2025-08-17 11:01 本頁面
【正文】 課 程 設(shè) 計 報 告課程設(shè)計名稱： 算法設(shè)計與分析系 ： 三系 學(xué)生姓名： 吳 陽 班 級： 12軟件(2)班 學(xué) 號： 20120311232 成 績： 指導(dǎo)教師： 秦川 開課時間： 2014 學(xué)年 一 學(xué)期一、問題描述1．普通背包問題給定n種物品和一個背包。物品i的重量是Wi,其價值為Vi,背包的容量為C。選擇裝入的背包的物品，使得裝入背包中的物品的總價值最大，在選擇物品i裝入背包時，可以選擇物品i的一部分，而不一定要全部裝入背包，1≤i≤n。2．0/1背包問題給定n種物品和一個背包。物品i的重量是Wi,其價值為Vi,背包的容量為C。選擇裝入的背包的物品，使得裝入背包中的物品的總價值最大，在選擇物品i裝入背包時，對于每種物品i只有兩種選擇，即裝入背包或者不裝入背包，不能將物品裝入背包多次，也不能只裝入部分的物品i。 3．棋盤覆蓋問題在一個2k x 2k個方格組成的棋盤中恰有一個方格與其他的不同稱為特殊方格，想要求利用四種L型骨牌（每個骨牌可覆蓋三個方格）不相互重疊覆蓋的將除了特殊方格外的其他方格覆蓋。二、問題分析1．普通背包問題對于背包問題，若它的一個最優(yōu)解包含物品j，則從該最優(yōu)解中拿出所含的物品j的那部分重量Ｗ，剩余的將是n1個原重物品1，2，，j1，j+1，，n以及重為Ｗi－Ｗ的物品j中可裝入容量為C－Ｗ的背包且具有最大價值的物品。2．0/1背包問題如果當(dāng)前背包中的物品的總?cè)萘渴莄w，前面的k1件物品都已經(jīng)決定好是否要放入包中，那么第k件物品是否放入包中取決于不等式 cw + wk = M (其中，wk為第k件物品的容量，M為背包的容量)（此即約束條件） 然后我們再尋找限界函數(shù)，這個問題比較麻煩，我們可以回憶一下背包問題的貪心算法，即物品按照 物品的價值/物品的體積 來從大到小排列，然后最優(yōu)解為（1，1，1.......，1，t，0，0，......），其中0=t=1； 因此，我們在確定第k個物品到底要不要放入的時候(在前k1個物品已經(jīng)確定的情況下)，我們可以考慮我們能夠達(dá)到的最大的價值，即我們可以通過計算只放入一部分的k物品來計算最大的價值。我們要確保當(dāng)前選擇的路徑的最大的價值要大于我們已經(jīng)選擇的路徑的價值。這就是該問題的限界條件。通過該條件，可以減去很多的枝條，大大節(jié)省運(yùn)行時間。3．棋盤覆蓋問題每次都對分割后的四個小方塊進(jìn)行判斷，判斷特殊方格是否在里面。這里的判斷的方法是每次先記錄下整個大方塊的左上角方格的行列坐標(biāo)，然后再與特殊方格坐標(biāo)進(jìn)行比較，就可以知道特殊方格是否在該塊中。如果特殊方塊在里面，這直接遞歸下去求即可，如果不在，這根據(jù)分割的四個方塊的不同位置，把右下角、左下角、右上角或者左上角的方格標(biāo)記為特殊方塊，然后繼續(xù)遞歸。在遞歸函數(shù)里，還要有一個變量s來記錄邊的方格數(shù)，每次對方塊進(jìn)行劃分時，邊的方格數(shù)都會減半，這個變量是為了方便判斷特殊方格的位置。其次還要有一個變nCount來記錄L型骨牌的數(shù)量。三、建立數(shù)學(xué)模型1．普通背包問題普通背包問題的數(shù)學(xué)描述為：在選擇物品i裝入背包時，可以選擇物品i的一部分，而不一定要全部裝入背包，1≤i≤n。C0,wi0,vi0,1≤i≤n,要求找出一個n元01向量（x1,x2,x3,，xn）,xi∈{0,1}，1≤i≤n,使得≤C,而且達(dá)到最大。2．0/1背包問題01背包問題的數(shù)學(xué)描述為：不能將物品裝入背包多次，也不能只裝入部分的物品i。 C0,wi0,vi0,1≤i≤n,要求找出一個n元01向量（x1,x
畢業(yè)設(shè)計相關(guān)推薦
鄂ICP備17016276號-1