已知鋼材的總長，訂單數和各訂單需要的長度編制程序從訂單中選擇一組訂單對鋼材作切割加工， 使得鋼材得到最佳應用，約定，每次切割損耗固定長度的鋼材。 下面寫一下我的思路，剛開始沒有想明白應該怎么使用遞歸去做，但是，看了他們的代碼之后，走了一遍，才明白，其實思路不太好想，但是實現起來還是比較容易的。 假設，我們有一段鋼材，長度為12米，其中有3個訂單，分別需要的長度為5,6,9米，每次切割總會有2米的損耗，求得其最佳訂單組合。 現在我們想想一下我們正常的思路： 如果是只有一個訂單的話，9米的訂單是最合適的，加上2米的耗材，一共11米。 如果有兩個訂單的話，有組合5,6；5,9；6,9這三個組合，很明顯，這三個組合都已經超過了12米的長度，因為如果是5,6的話，雖然說訂單的和為11，但是有兩次切割，還會有4米的耗材，加起來就是15米，已經遠遠超過鋼材的長度了 由上面的可以知道，3個訂單的組合那就更不行了。 那我們應該如何做到實現這個思路呢，我們有一個數組記錄訂單是否選中，請看下面這張圖：  5,6,9初始化的時候，全是未選中的狀態，程序開始執行，先選中5，加上損耗的長度小于12，則繼續選中6，這樣加上損耗的長度大于12了，則設置6的狀態為未選中；接著選中9,5加上9加上損耗的長度，很明顯超過12了，那么設置9的狀態為未選中；接著從5開始的遍歷完成了，將5的狀態設置為未選中；選中6，再從5開始選中，這樣進行下去。。。。 當然，中間需要有兩個變量記錄最佳長度和最佳訂單組合。 下面附上我的代碼： ~~~ #include <stdio.h> /** * 已知鋼材的總長，訂單數和各訂單需要的長度 * 編制程序從訂單中選擇一組訂單對鋼材作切割加工， * 使得鋼材得到最佳應用，約定，每次切割損耗 * 固定長度的鋼材 */ #define N 20 #define DELTA 2 //切割鋼材損耗 /**最好的長度 **/ int bestlen; /**最好長度的選定訂單 **/ int bestsele[N]; /**選定訂單，用于嘗試選擇 **/ int sele[N]; /**有n的訂單 **/ int n; /**訂單需要的鋼材的長度 **/ int orderlen[N]; /**鋼材總長度 **/ int total; void attempt(); int main(void) { int j; //獲取鋼材的總長度 printf("Please enter the length of the steel:\n"); scanf("%d",&total); //獲取鋼材的訂單數 printf("Please enter the number of the orders:\n"); scanf("%d",&n); //獲取各個訂單數需要的長度 printf("Please enter the length of every order:\n"); for(j = 0;j < n;j++) scanf("%d",&orderlen[j]); //初始化工作,使所有的訂單都沒有被選中 for(j = 0;j < n;j++) bestsele[j] = sele[j] = 0; //初始化最佳長度，設置為0 bestlen = 0; //獲取最佳長度 attempt(); printf("order:\n"); for(j = 0;j < n;j++){ if(bestsele[j]) printf("%d\t",orderlen[j]); } printf("\nlength:\n%d",bestlen); return 0; } void attempt(){ int i,len; //獲取選中的訂單的總長度（加上損耗） for(len = i = 0;i < n;i++) if(sele[i]) len += (orderlen[i]+DELTA); if(len-DELTA <= total){ //注意，最后一個訂單可能不需要損耗 if(bestlen < len){ bestlen = len; for(i = 0;i < n;i++) bestsele[i] = sele[i]; } //每次嘗試選擇訂單之后，需要將其還原未選中狀態 for(i = 0;i < n;i++){ if(!sele[i]){ sele[i] = 1; attempt(); sele[i] = 0; } } } } ~~~