【正文】 nclude iostreaminclude vectorinclude algorithmusing namespace std。int n , l。int greedy(vectorintx ,int m ){ int i = 0 , sum = 0 , n=()。 sort((),() ) 。 while( i n ) { sum += x[i] 。 if( sum = m ) i ++ 。 else return i 。 } return n 。}int main(){ int i ,a[1000]。 vectorint x。 cin n l 。 for( i = 0 。 i n 。 i ++ ) { cina[i]。(a[i])。 } cout greedy( x , l ) endl。return 0 。}1048 Optimal Services設(shè)有n 個(gè)顧客同時(shí)等待一項(xiàng)服務(wù)。顧客i需要的服務(wù)時(shí)間為ti ，1 ≤ i ≤ n。應(yīng)如何安排n個(gè)顧客的服務(wù)次序才能使平均等待時(shí)間達(dá)到最小?平均等待時(shí)間是n 個(gè)顧客等待服務(wù)時(shí)間的總和除以n。 編程任務(wù)： 對(duì)于給定的n個(gè)顧客需要的服務(wù)時(shí)間，編程計(jì)算最優(yōu)服務(wù)次序。Input 輸入由多組測(cè)試數(shù)據(jù)組成。 每組測(cè)試數(shù)據(jù)輸入的第一行是正整數(shù)n，表示有n 個(gè)顧客。接下來(lái)的1行中，有n個(gè)正整數(shù)，表示n個(gè)顧客需要的服務(wù)時(shí)間。Output 對(duì)應(yīng)每組輸入，輸出的每行是計(jì)算出的最小平均等待時(shí)間。Sample Input 1056 12 1 99 1000 234 33 55 99 812Sample Output includeiostreamincludealgorithmusing namespace std。int s[100000],n,i。int main(){ while(scanf(%d,amp。n)!=EOF){ for(i=0。in。i++)scanf(%d,amp。s[i])。sort(amp。s[0],amp。s[n])。int sum=0。for(i=0。in。i++){ sum+=s[i]*(ni)。 }float ans=float(sum)/float(n)。printf(%.2f\n,ans)。 }return 0。}1049 汽車(chē)加油問(wèn)題一輛汽車(chē)加滿油后可行駛n公里。旅途中有若干個(gè)加油站。設(shè)計(jì)一個(gè)有效算法，指出應(yīng)在哪些加油站停靠加油，使沿途加油次數(shù)最少。并證明算法能產(chǎn)生一個(gè)最優(yōu)解。 編程任務(wù)： 對(duì)于給定的n和k個(gè)加油站位置，編程計(jì)算最少加油次數(shù)。Input 輸入由多組測(cè)試數(shù)據(jù)組成。 每組測(cè)試數(shù)據(jù)輸入的第一行有2 個(gè)正整數(shù)n和k，表示汽車(chē)加滿油后可行駛n公里，且旅途中有k個(gè)加油站。接下來(lái)的1 行中，有k+1 個(gè)整數(shù)，表示第k個(gè)加油站與第k1 個(gè)加油站之間的距離。第0 個(gè)加油站表示出發(fā)地，汽車(chē)已加滿油。第k+1 個(gè)加油站表示目的地。Output 對(duì)應(yīng)每組輸入，輸出的每行是計(jì)算出的最少加油次數(shù)。如果無(wú)法到達(dá)目的地，則輸出”No Solution”。Sample Input 7 71 2 3 4 5 1 6 6Sample Output 4include iostreaminclude vectorusing namespace std。int a[1000]。int g(vectorint x, int n ){ int i , j , s 。 int sum = 0 , k = ()。 for( j = 0 。 j k 。 j ++ ) if( x[j] n ) { coutNo Solution!endl。 return 1。 } for( i = 0 , s = 0 。 i k 。 i ++ ) { s+= x[i]。 if(sn) { sum++。 s=x[i]。 } } return sum 。}int main(){ int i , n , k , tmp。 vectorintx。 cin n k。 for( i = 0 。 i = k 。 i++ ) { cin a[i]。 (a[i])。 } tmp = g(x,n)。 if(tmp!=1) couttmpendl。 return 0。}1059 Problem A 子集樹(shù)問(wèn)題Description 試設(shè)計(jì)一個(gè)用回溯法搜索子集空間樹(shù)的函數(shù)。該函數(shù)的參數(shù)包括結(jié)點(diǎn)可行性判定函數(shù)和上界函數(shù)等必要的函數(shù)，并將此函數(shù)用于解裝載問(wèn)題。 裝載問(wèn)題描述如下：有一批共n(n≤≡10)個(gè)集裝箱要裝上艘載重量為c的輪船，其中集裝箱i的重量為wi。找出一種最優(yōu)裝載方案，將輪船盡可能裝滿，即在裝載體積不受限制的情況下，將盡可能重的集裝箱裝上輪船。Input 輸入由多組測(cè)試數(shù)據(jù)組成。 每組測(cè)試數(shù)據(jù)輸入的第一行有2個(gè)正整數(shù)n和c，n是集裝箱數(shù)，c是輪船的載重量。接下來(lái)的1行中有n個(gè)正整數(shù)，表示集裝箱的重量。Output 對(duì)應(yīng)每組輸入，輸出的每行是將計(jì)算出的最大裝載重量。Sample Input 5 107 2 6 5 4Sample Output 10include iostreamdefine MAX 12882using namespace std。struct node{int w。}data[MAX]。int dp[MAX],n,m。void Init(){int i。for(i=1。i=n。i++)scanf(%d,amp。data[i].w)。}int GetMax(int a,int b){if(ab)return a。elsereturn b。}void Knapsack(){int i,j。for(i=0。i=m。i++){if(i=data[n].w)dp[i]=data[n].w。elsedp[i]=0。}for(i=n1。i=1。i)for(j=m。j=1。j){if(j=data[i].w){dp[j]=GetMax(dp[j],dp[jdata[i].w]+data[i].w)。}elsebreak。}}int main(){while(scanf(%d%d,amp。n,amp。m)!=EOF){Init()。Knapsack()。printf(%d\n,dp[m])。}return 0。}1060 Problem B 01 KnapsackDescription 試設(shè)計(jì)一個(gè)用回溯法搜索子集空間樹(shù)的函數(shù)。該函數(shù)的參數(shù)包括結(jié)點(diǎn)可行性判定函數(shù)和上界函數(shù)等必要的函數(shù)，并將此函數(shù)用于解01背包問(wèn)題。 01 背包問(wèn)題描述如下：給定n 種物品和一個(gè)背包。物品i的重量是wi，其價(jià)值為vi ，背包的容量為C。應(yīng)如何選擇裝入背包的物品，使得裝入背包中物品的總價(jià)值最大? 在選擇裝入背包的物品時(shí)，對(duì)每種物品i只有2 種選擇，即裝入背包或不裝入背包。不能將物品i 裝入背包多次，也不能只裝入部分的物品i。 Input 輸入由多組測(cè)試數(shù)據(jù)組成。 每組測(cè)試數(shù)據(jù)輸入的第一行有2個(gè)正整數(shù)n和c。n是物品數(shù)，c是背包的容量。接下來(lái)的1 行中有n個(gè)正整數(shù)，表示物品的價(jià)值。第3 行中有n個(gè)正整數(shù)，表示物品的重量。Output 對(duì)應(yīng)每組輸入，輸出的2行是裝入背包物品的最大價(jià)值和最優(yōu)裝入方案。Sample Input 5 106 3 5 4 62 2 6 5 4Sample Output 151 1 0 0 1include includeincludeint min(int w,int c){int temp。if (wc) temp=w。elsetemp=c。return temp。}int max(int w,int c){int temp。if (wc) temp=w。elsetemp=c。return temp。}void knapsack(int v[],int w[],int c,int n,int**m) {int jmax=min(w[n]1,c)。for(int j=0。j=jmax。j++)m[n][j]=0。for(int jj=w[n]。jj=c。jj++)m[n][jj]=v[n]。for(int i=n1。i1。i){ jmax=min(w[i]1,c)。for(int j=0。j=jmax。j++)m[i][j]=m[i+1][j]。for(int jj=w[i]。jj=c。jj++)m[i][jj]=max(m[i+1][jj],m[i+1][jjw[i]]+v[i])。}m[1][c]=m[2][c]。if(c=w[1])m[1][c]=max(m[1][c],m[2][cw[1]]+v[1])。coutm[1][c]endl。}int traceback(int **m,int w[],int c,int n,int x[]) {for(int i=1。in。i++)if(m[i][c]==m[i+1][c]) x[i]=0。else {x[i]=1。c=w[i]。}x[n]=(m[n][c])?1:0。for(int y=1。y=n。y++){coutx[y] 。}coutendl。return x[n]。}int main(){int n,c。int **m。cinnc。int *v=new int[n+1]。for(int i=1。i=n。i++)cinv[i]。int *w=new int[n+1]。for(int j=1。j=n。j++)cinw[j]。int *x=new int[n+1]。m=new int*[n+1]。 for(int p=0。pn+1。p++){m[p]=new int[c+1]。}knapsack(v,w,c,n,m)。traceback(m,w,c,n,x)。delete []x。delete []w。delete []v。return 0。}1061 Problem C 排列樹(shù)問(wèn)題Description 試設(shè)計(jì)一個(gè)用回溯法搜索排列空間樹(shù)的函數(shù)。該函數(shù)的參數(shù)包括結(jié)點(diǎn)可行性判定函數(shù)和上界函數(shù)等必要的函數(shù)，并將此函數(shù)用于解圓排列問(wèn)題。 圓排列問(wèn)題描述如下：給定n 個(gè)大小不等的圓c1 , c2 ,..., ，現(xiàn)要將這n 個(gè)圓排進(jìn)一個(gè)矩形框中，且要求各圓與矩形框的底邊相切。圓排列問(wèn)題要求從n 個(gè)圓的所有排列中找出有最小長(zhǎng)度的圓排列。例如，當(dāng)n=3，且所給的3 個(gè)圓的半徑分別為1，1，2 時(shí)，這3 個(gè)圓的最小長(zhǎng)度的圓排列是1,2,1，其最小長(zhǎng)度為2 + 4*sqr(2)。 編程任務(wù)： 對(duì)于給定的n(n≤≡10)個(gè)圓，編程計(jì)算最小長(zhǎng)度排列。 Input 輸入由多組測(cè)試數(shù)據(jù)組成。每組測(cè)試數(shù)據(jù)輸入的第一行是1 個(gè)正整數(shù)n，表示有n個(gè)圓。第2行有n個(gè)正數(shù)，分別表示n個(gè)圓的半徑。Output 對(duì)應(yīng)每組輸入，輸出的每行是計(jì)算出的最小長(zhǎng)度，保留3 位小數(shù)。Sample Input 31 1 2Sample Output include iostreaminclude iomanipusing namespace std。include float rr[11]={}。class Circle{public:Circle(int, float *)。~Circle()。void Backtrack(int)。void Print()。private:float Center(int)。void Compute(void)。void Swa