c語言課程設計背包問題的求解報告

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

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

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

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