算法設計與分析期末論(編輯修改稿)
2025-07-13 01:59 本頁面
【文章內容簡介】 時輸出 minexpense： 4； 輸出路徑時：只輸出二維數(shù)組 c[][]中第 i 行中第 q[i]個數(shù)，其他輸出空格 結果為 1 2 5 1 源代碼注釋 include include define N 100 int q[N]={0}。//全局變量 int minexpense=1。//最小費用 void workdistribute(int i,int n, int p[],int x[],int c[][N])。//遞歸函數(shù) void main() { int n=0。 int c[N][N]。 int x[N]={0}。 int p[N]={0}。 printf(\t\t\t01 工作分配問題 \n)。 printf(請輸入人數(shù) \n)。 scanf(%d,amp。n)。 for(int i=1。i=n。i++)//輸入數(shù)組 C { for(int j=1。j=n。j++) scanf(%d,amp。c[i][j])。 } workdistribute(1,n,p,x,c)。//進行分配 printf(%d\n,minexpense)。 for(int k=1。k=n。k++) { for(int j=1。j=n。j++) { if(q[k]!=j) printf( )。 else printf(%d ,c[k][j])。//輸出分配路徑 } printf(\n)。 } } void workdistribute(int i,int n,int *p,int x[],int c[][N]) { for(int j=1。j=n。j++)//數(shù)組每一行的列循環(huán) { if(x[j]==0)//i 行 j 列沒分配則進行分配 { 6 x[j]=1。 x[0]+=c[i][j]。 p[i]=j。 if(in) { workdistribute(i+1,n,p,x,c)。 } else//判斷最后一事件分配完后，判斷 此次分配是不是最小費用 { if(minexpensex[0]||minexpense==1) //如果是最小分配或第一次分配，則保存此次分配數(shù)據(jù) { minexpense=x[0]。 for(int k=1。k=n。k++) q[k]=p[k]。 } } x[j]=0。 x[0]=c[i][j]。//當此事件及以后的事件分配完后， //返回上事件進行下一次分配前減去此次事件分配所需費用 } } } 運行結果 7 給定 n 種物品和一背包。物品 i 的重量是 wi，其價值為 vi，背包的容量為 C。問應如何選擇裝入背包中的物品，使得裝入背包中物品的總價值最大？要求對每種物品i 裝入背包或不裝入背包。不能將物品 i 裝入背包多次，也不能只裝入部分的物品 i（要求使用遞歸法實現(xiàn)）。 設計算法 在選擇裝入背包的物品時，對每種物品 i 只有兩種選擇，即裝入背包或不裝入背包。不能將物品 i 裝入背包多次，也不能只裝入部分的物品 i，因此，該問題稱為背包問題。 此問題的形式化描述是，給定 C0,wi,vi0， 1≤i≤n,要求找出 n 元 01 的向量( 1x , 2x ,..., nx ),ix ?{0,1},1≤i≤n,使得iixw??n1i ≤C，而且 iix??n1i v 達到最大。因此， 01 背包問題是一個特殊的整數(shù)規(guī)劃問題。 設所給 01 背包問題的子問題 ?????? ??????
畢業(yè)設計相關推薦
鄂ICP備17016276號-1