算法設(shè)計(jì)與分析期末論-資料下載頁
2025-06-07 01:59本頁面
【正文】 后 i=5n=4，返回上一層，遞歸結(jié)束 x[1]~x[4]={1,0,1,1}。 回到 main 函數(shù)輸出背包最大價(jià)值 9，以及放入物品重量和價(jià)值 [1,2]， [2,4]， [3,3]。 程序結(jié)束。 程序源代碼及注釋 include define N 50 int knapsack(int i,int n,int v[],int w[],int c,int m[][N])。//計(jì)算最大價(jià)值遞歸函數(shù) int traceback(int i, int m[][N],int w[],int c)。//尋找所放物品遞歸函數(shù) int x[N]={0}。//用來標(biāo)記物品是否被放入 void main() { int w[N]={0},v[N]={0}。 int m[N][N]={0}。 int C=0,n=0。 printf(\t\t \n)。 printf(輸入背包容量 :\n)。 scanf(%d,amp。C)。 printf(輸入物體數(shù)量 :\n,amp。n)。 scanf(%d,amp。n)。 printf(輸入物體重量和價(jià)值 \n)。 for(int i=1。i=n。i++) { 10 scanf(%d %d,amp。w[i],amp。v[i])。 w[0]++。 } printf(最大價(jià)值為： %d\n,knapsack(1, w[0],v,w,C,m))。 printf(所放物品重量和價(jià)值為： \n)。 printf(重量 價(jià)值 \n)。 for( i=1。i=w[0]。i++) { if(x[i]==1) printf( %d %d\n,w[i],v[i])。//輸出所放物品重量和價(jià)值 } scanf(%d,amp。n)。 } int knapsack(int i, int n,int v[],int w[],int c,int m[][N]) { if(i==n)//當(dāng)裝最低的物品時(shí) for(int j=1。j=c。j++) { if(w[i]=j) { m[i][j]=v[i]。 x[i]=1。 } else m[i][j]=0。 } else if(i=1)//裝不是最底層物品時(shí) 11 { knapsack(i+1,n, v,w,c,m)。//繼續(xù)遞歸，裝 i 層下物品 for(int j=1。j=c。j++) { if(j=w[i]amp。amp。m[i+1][j]=m[i+1][jw[i]]+v[i])//當(dāng)背包容量不小于物品重 量時(shí)的最優(yōu)放法 { m[i][j]=m[i+1][jw[i]]+v[i]。 } else//當(dāng)背包容量小于物品重量時(shí) m[i][j]=m[i+1][j]。 } } if(i==1)//當(dāng)所有物品都遍歷后，構(gòu)造最優(yōu)解 traceback(i,m,w,c)。 return m[i][c]。//反會(huì)背包最大價(jià)值 } int traceback(int i, int m[][N],int w[],int c)//構(gòu)造最優(yōu)解遞歸函數(shù) { if(iw[0]) return 0。 if(m[i][c]==m[i+1][c])//當(dāng)背包價(jià)值數(shù)組第 i 行最后的值于下行最后值相同，第 i 個(gè)物品不放 { x[i]=0。 traceback(i+1,m,w,c)。//從下一行繼續(xù)構(gòu)造最優(yōu)解 } else////當(dāng)背包價(jià)值數(shù)組第 i 行最后的值于下行最后值不相同，第 i 個(gè)物品放入背包 12 { x[i]=1。 traceback(i+1,m,w,cw[i])。 } } 程序運(yùn)行結(jié)果截圖
畢業(yè)設(shè)計(jì)相關(guān)推薦
鄂ICP備17016276號(hào)-1