c語(yǔ)言課程設(shè)計(jì)背包問(wèn)題的求解報(bào)告

1、東莞理工學(xué)院課程設(shè)計(jì)11 問(wèn)題要求及任務(wù)描述 問(wèn)題要求及任務(wù)描述1.1 題目要求背包問(wèn)題的求解 背包問(wèn)題的求解問(wèn)題描述：假設(shè)有一個(gè)能裝入總體積為 T 的背包和 n 件體積分別為 w1 , w2 , … , wn 的物品，能否從 n件物品中挑選若干件恰好裝滿背包，即使 w1 +w2 + … + wn=T，要求找出所有滿足上述條件的解。例如：當(dāng) T=10，各件物品的體積{1，8，4，3，5，2}時(shí)，可找到下列 4

2、組解：（1，4，3，2）（1，4，5）（8，2）（3，5，2） 。1.2 主要任務(wù)尋找所有的解法。2 解決問(wèn)題的主要思路和方法 解決問(wèn)題的主要思路和方法2.1 關(guān)鍵問(wèn)題如何不遺漏地找出所有的解法。2.2 擬采用解決問(wèn)題的方法利用回溯法的設(shè)計(jì)思想來(lái)解決背包問(wèn)題。首先將物品排成一列，然后順序 選取物品裝入背包，假設(shè)已選取了前 i 件物品之后背包還沒(méi)有裝滿，則繼續(xù)選取第 i+1 件物品，若該件物品“太大“不能裝入，則棄之而繼續(xù)選取下一件，

3、直 至背包裝滿為止。但如果在剩余的物品中找不到合適的物品以填滿背包，則說(shuō)明“剛剛“裝入背包的那件物品“不合適“，應(yīng)將它取出“棄之一邊“，繼續(xù)再?gòu)摹八?之后“的物品中選取，如此重復(fù)，直至求得滿足條件的解。2.3 主要算法和處理流程圖利用多重循環(huán)結(jié)構(gòu)來(lái)尋找正確的解。東莞理工學(xué)院課程設(shè)計(jì)3sum=sum-w[i]-w[k-1];i=k;k--;}k++;}}/*內(nèi)循環(huán)結(jié)束 內(nèi)循環(huán)結(jié)束*/}/*外循環(huán)結(jié)束 外循環(huán)結(jié)束*/}main()/*主函數(shù)

4、 主函數(shù)*/{int i,j;int w[100],n,t;printf(“題目：背包問(wèn)題的求解 題目：背包問(wèn)題的求解\n“);printf(“請(qǐng)輸入總體積 請(qǐng)輸入總體積\n“);scanf(“%d“,printf(“請(qǐng)輸入物品數(shù)目 請(qǐng)輸入物品數(shù)目\n“);scanf(“%d“,printf(“請(qǐng)輸入各物品重量 請(qǐng)輸入各物品重量\n“);for(i=0;i<n;i++)/*輸入各物品的重量 輸入各物品的重量*/{scanf(“%d