• <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為偶數時求出s(n,n/2),n為奇數時 也是s(2n,n/2),和sum/2最接近的那個。非常經典的思路。
            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--)//遞減的結果是使得不會出現在同一層次的互為因果 、、、、、、、、、、、巧妙的實現了課本上的序偶對生成法。
               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;
              }
            下一次實現一個序偶生成法。

            #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)  編輯 收藏 引用 所屬分類: 動態規劃給我啟發題
            <2009年7月>
            2829301234
            567891011
            12131415161718
            19202122232425
            2627282930311
            2345678

            常用鏈接

            留言簿(3)

            隨筆分類

            隨筆檔案

            文章分類

            文章檔案

            友情鏈接

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

            亚洲精品高清久久| 久久99精品国产麻豆宅宅| 国内精品久久人妻互换| 精品一区二区久久| 久久久久亚洲精品无码网址 | 亚洲а∨天堂久久精品| 麻豆av久久av盛宴av| 久久久青草久久久青草| 亚洲午夜无码AV毛片久久| 精品久久久久久亚洲精品| 久久免费香蕉视频| 精品亚洲综合久久中文字幕| 亚洲精品久久久www| 精品久久久无码人妻中文字幕豆芽| 久久综合久久久| 人妻丰满AV无码久久不卡| 久久精品二区| 久久最新精品国产| 久久综合给合久久国产免费 | 久久精品无码一区二区无码 | 7777精品久久久大香线蕉| 66精品综合久久久久久久| 亚洲精品乱码久久久久久| 久久人人爽人爽人人爽av| 久久久精品免费国产四虎| 老男人久久青草av高清| 亚洲国产成人乱码精品女人久久久不卡| 久久久久女人精品毛片| 久久久久久久波多野结衣高潮 | 人妻少妇久久中文字幕 | 综合久久国产九一剧情麻豆| 国产精品成人99久久久久 | 精品久久久中文字幕人妻| 91精品婷婷国产综合久久| 久久91精品久久91综合| 国产亚洲色婷婷久久99精品| 日韩精品无码久久久久久| 久久九九精品99国产精品| 亚洲综合伊人久久综合| 亚洲乱码精品久久久久..| 少妇内射兰兰久久|