• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            posts - 195,  comments - 30,  trackbacks - 0

            Tug of War


            Status In/Out TIME Limit MEMORY Limit Submit Times Solved Users JUDGE TYPE
            stdin/stdout 15s 8192K 479 114 Standard

            A tug of war is to be arranged at the local office picnic. For the tug of war, the picnickers must be divided into two teams. Each person must be on one team or the other; the number of people on the two teams must not differ by more than 1; the total weight of the people on each team should be as nearly equal as possible.

            The first line of input contains n the number of people at the picnic. n lines follow. The first line gives the weight of person 1; the second the weight of person 2; and so on. Each weight is an integer between 1 and 450. There are at most 100 people at the picnic.

            The input may contain several test cases.

            Your output will be a single line containing 2 numbers: the total weight of the people on one team, and the total weight of the people on the other team. If these numbers differ, give the lesser first.

            Sample Input

            3
            100
            90
            200
            

            Output for Sample Input

            190 200
            


            利用dp思想 ,n為偶數(shù)時求出s(n,n/2),n為奇數(shù)時 也是s(2n,n/2),和sum/2最接近的那個。非常經(jīng)典的思路。
            S(k, 1) = {A[i] | 1<= i <= k}
            S(k, k) = {A[1]+A[2]+…+A[k]}
            S(k, i) = S(k-1, i) U {A[k] + x | x屬于S(k-1, i-1) }
            //一下代碼只能用于sum特別小的情況,否則會超時!!!!!!!!!!!
            #include<iostream>
            #include<cstdlib>
            #define MAX 101
            #define min(a,b) ((a)<(b) ? (a) : (b))
            using namespace std;

              int main()
              {
              freopen("s.txt","r",stdin);
              freopen("key.txt","w",stdout);
              int num;
              int a[MAX],i,j,k,l,m,NUM;
              bool s[MAX][2500];
              while(cin>>num)
              {
              int sum=0;
                for(i=1;i<=num;i++)
               {
              cin>>a[i];
              sum+=a[i]; 
               }
               if(num%2==0)NUM=num/2;
               else NUM=num/2+1;

                for(i=0;i<=num;i++)
                 for(j=0;j<=sum/2;j++)
                  s[i][j]=false;//表示取i個物品能否達到重量是j.
                 
               s[0][0]=true;
               for(k=1;k<=num;k++)//必須在最外層,元素不能重復
               for(j=min(k,NUM);j>=1; j--)//遞減的結果是使得不會出現(xiàn)在同一層次的互為因果 、、、、、、、、、、、巧妙的實現(xiàn)了課本上的序偶對生成法。
               for(i=a[k];i<=sum/2;i++)
               {
              if(s[j-1][i-a[k]])
              s[j][i]=true;
             }
             
             for(i=sum/2; i>=0; i--) {  
                if(s[NUM][i]) {  
                    cout <<i<<" "<<sum-i<<endl;  
                    break;  
                }  

              }
              //system("PAUSE");
              return   0;
              }
            下一次實現(xiàn)一個序偶生成法。

            #include <iostream>
            #include <functional>
            using namespace std;

            int a[101];
            bool b[101][45002];

            int main(){
            // freopen("s.txt","r",stdin);
            //  freopen("key.txt","w",stdout);
                int N,M,i,j,k;
                while(scanf("%d",&N)!=EOF){
                     memset(b,0,sizeof(b));
                     a[0]=M=0;
                    for(i=1;i<=N;i++){
                         scanf("%d",a+i);
                         M+=a[i];
                     }
                     b[0][0]=1;
                    for(k=1;k<=N;k++){
                        for(i=1;i<=N/2;i++){
                            for(j=M/2;j>=0;j--){
                                if(b[i-1][j]){
                                     b[i][j+a[k]]=1;
                                 }
                             }
                         }
                     }
                    for(i=M/2,j=M/2+1;i>=0;i--,j++){
                        if(b[N/2][i]){
                             printf("%d %d\n",i,M-i);
                            break;
                         }
                        if(b[N/2][j]){
                             printf("%d %d\n",M-j,j);
                            break;
                         }
                     }
                 }
                return 0;
            }

            posted on 2009-07-02 16:05 luis 閱讀(544) 評論(0)  編輯 收藏 引用 所屬分類: 動態(tài)規(guī)劃給我啟發(fā)題
            <2011年11月>
            303112345
            6789101112
            13141516171819
            20212223242526
            27282930123
            45678910

            常用鏈接

            留言簿(3)

            隨筆分類

            隨筆檔案

            文章分類

            文章檔案

            友情鏈接

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

            久久天天躁夜夜躁狠狠| 久久国产精品99精品国产| 国产精品综合久久第一页| 久久乐国产精品亚洲综合| 久久精品国产日本波多野结衣| 亚洲AV无码久久精品成人| 亚洲综合婷婷久久| 99久久精品免费看国产一区二区三区 | 亚洲美日韩Av中文字幕无码久久久妻妇 | 久久精品这里热有精品| 中文字幕精品久久| 精品久久久久久久久午夜福利| 中文精品久久久久国产网址 | 久久精品国产亚洲AV无码娇色| 久久国产精品视频| 久久综合狠狠综合久久| 一本色道久久综合| 久久精品国产亚洲精品| 久久久女人与动物群交毛片 | 亚洲天堂久久精品| 精品熟女少妇AV免费久久| 久久精品国产亚洲av瑜伽| 精品亚洲综合久久中文字幕| 久久人人添人人爽添人人片牛牛| 情人伊人久久综合亚洲| 国产精品久久久久国产A级| 久久亚洲精品国产精品| 国产成人久久精品一区二区三区| 久久精品一区二区三区中文字幕| 久久精品国产精品亚洲精品| 国产精品久久影院| 久久99精品国产99久久6男男| 久久精品中文闷骚内射| 97久久超碰成人精品网站| 精品久久久久久久无码 | 欧美久久天天综合香蕉伊| 久久国产精品波多野结衣AV| 久久久久久A亚洲欧洲AV冫| 久久夜色精品国产www| 久久涩综合| 中文字幕无码免费久久|