算法設(shè)計(jì)與分析課程設(shè)計(jì)報(bào)告-在線瀏覽
2024-09-15 11:01本頁(yè)面
【正文】 量，M為背包的容量)（此即約束條件） 然后我們?cè)賹ふ蚁藿绾瘮?shù)，這個(gè)問(wèn)題比較麻煩，我們可以回憶一下背包問(wèn)題的貪心算法，即物品按照 物品的價(jià)值/物品的體積 來(lái)從大到小排列，然后最優(yōu)解為（1，1，1.......，1，t，0，0，......），其中0=t=1； 因此，我們?cè)诖_定第k個(gè)物品到底要不要放入的時(shí)候(在前k1個(gè)物品已經(jīng)確定的情況下)，我們可以考慮我們能夠達(dá)到的最大的價(jià)值，即我們可以通過(guò)計(jì)算只放入一部分的k物品來(lái)計(jì)算最大的價(jià)值。這就是該問(wèn)題的限界條件。3．棋盤(pán)覆蓋問(wèn)題每次都對(duì)分割后的四個(gè)小方塊進(jìn)行判斷，判斷特殊方格是否在里面。如果特殊方塊在里面，這直接遞歸下去求即可，如果不在，這根據(jù)分割的四個(gè)方塊的不同位置，把右下角、左下角、右上角或者左上角的方格標(biāo)記為特殊方塊，然后繼續(xù)遞歸。其次還要有一個(gè)變nCount來(lái)記錄L型骨牌的數(shù)量。C0,wi0,vi0,1≤i≤n,要求找出一個(gè)n元01向量（x1,x2,x3,2．0/1背包問(wèn)題01背包問(wèn)題的數(shù)學(xué)描述為：不能將物品裝入背包多次，也不能只裝入部分的物品i。xn）,xi∈{0,1}，1≤i≤n,使得≤C,而且達(dá)到最大。特殊方格必位于4個(gè)較小子棋盤(pán)之一中，其余3個(gè)子棋盤(pán)中無(wú)特殊方格。遞歸地使用這種分割，直至棋盤(pán)簡(jiǎn)化為棋盤(pán)11。算法設(shè)計(jì)：首先計(jì)算每種物品單位重量的價(jià)值Vi/Wi，然后按單位重量?jī)r(jià)值從大到小進(jìn)行排序，根據(jù)貪心選擇策略，將盡可能多的單位重量?jī)r(jià)值最高的物品裝入背包。2．0/1背包問(wèn)題該01背包問(wèn)題采用的是回溯算法，回溯算法的基本解題步驟是： （1）針對(duì)所給問(wèn)題定義問(wèn)題的解空間； （2）確定易于搜索的解空間結(jié)構(gòu)； （3）以深度優(yōu)先方式搜索解空間，并在搜索過(guò)程中用剪枝函數(shù)避免無(wú)效的搜索。3．棋盤(pán)覆蓋問(wèn)題該棋盤(pán)算法用的是分治算法，分治法解題的思路就是將大問(wèn)題化為若干子問(wèn)題，再依次解決子問(wèn)題，最后獲得問(wèn)題的答案。 （2） main()函數(shù)用來(lái)進(jìn)行輸入棋盤(pán)的大小和特殊棋盤(pán)的位置。 五、算法實(shí)現(xiàn)1．普通背包問(wèn)題include struct goodinfo{ float p。//物品重量 float x。//物品編碼}。 for (j=2。j++) { goods[0]=goods[j]。 while (goods[0].p goods[i].p ) { goods[i+1]=goods[i]。 } goods[i+1]=goods[0]。 int i,j。i=n。 cu=M。i=n。 //當(dāng)物品重量大于剩余容量時(shí)跳出 goods[i].x =1。//確定背包新的剩余容量 } if(i=n) { goods[i].x =cu/goods[i].w 。j=n。 i=j1。 i。 } printf(最優(yōu)解為：\n)。i=n。 printf(\n)。 int j,n。 goodinfo *goods。 scanf(%d,amp。 goods= new struct goodinfo[n+1]。 scanf(%f,amp。 printf(\n)。i=n。 printf(請(qǐng)輸入第%d個(gè)物品的重量：,i)。goods[i].w )。 scanf(%f,amp。 goods[i].p =goods[i].p /goods[i].w 。 } Insertionsort(goods,n)。 printf(如果繼續(xù)則選擇“1”，如果結(jié)束則選擇“0”\n)。j)。//物品的個(gè)數(shù)，背包的容量，最大價(jià)值int p[10000],w[10000],x[10000],bestx[10000]。 if(in)//回溯結(jié)束 {
畢業(yè)設(shè)計(jì)相關(guān)推薦
鄂ICP備17016276號(hào)-1