• <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>

            POJ 1015 Jury Compromise 動態規劃

            Description

            In Frobnia, a far-away country, the verdicts in court trials are determined by a jury consisting of members of the general public. Every time a trial is set to begin, a jury has to be selected, which is done as follows. First, several people are drawn randomly from the public. For each person in this pool, defence and prosecution assign a grade from 0 to 20 indicating their preference for this person. 0 means total dislike, 20 on the other hand means that this person is considered ideally suited for the jury.
            Based on the grades of the two parties, the judge selects the jury. In order to ensure a fair trial, the tendencies of the jury to favour either defence or prosecution should be as balanced as possible. The jury therefore has to be chosen in a way that is satisfactory to both parties.
            We will now make this more precise: given a pool of n potential jurors and two values di (the defence's value) and pi (the prosecution's value) for each potential juror i, you are to select a jury of m persons. If J is a subset of {1,..., n} with m elements, then D(J ) = sum(dk) k belong to J
            and P(J) = sum(pk) k belong to J are the total values of this jury for defence and prosecution.
            For an optimal jury J , the value |D(J) - P(J)| must be minimal. If there are several jurys with minimal |D(J) - P(J)|, one which maximizes D(J) + P(J) should be selected since the jury should be as ideal as possible for both parties.
            You are to write a program that implements this jury selection process and chooses an optimal jury given a set of candidates.

            Input

            The input file contains several jury selection rounds. Each round starts with a line containing two integers n and m. n is the number of candidates and m the number of jury members.
            These values will satisfy 1<=n<=200, 1<=m<=20 and of course m<=n. The following n lines contain the two integers pi and di for i = 1,...,n. A blank line separates each round from the next.
            The file ends with a round that has n = m = 0.

            Output

            For each round output a line containing the number of the jury selection round ('Jury #1', 'Jury #2', etc.).
            On the next line print the values D(J ) and P (J ) of your jury as shown below and on another line print the numbers of the m chosen candidates in ascending order. Output a blank before each individual candidate number.
            Output an empty line after each test case.

            Sample Input

            4 2
            1 2
            2 3
            4 1
            6 2
            0 0 

            Sample Output

            Jury #1
            Best jury has value 6 for prosecution and value 4 for defence:
            2 3 

            Hint

            If your solution is based on an inefficient algorithm, it may not execute in the allotted time.

            Source

             

                在遙遠的國家佛羅布尼亞,嫌犯是否有罪,須由陪審團決定。陪審團是由法官從公眾中挑選的。先隨機挑選n 個人作為陪審團的候選人,然后再從這n 個人中選m 人組成陪審團。選m 人的辦法是:控方和辯方會根據對候選人的喜歡程度,給所有候選人打分,分值從0 到20。為了公平起見,法官選出陪審團的原則是:選出的m 個人,必須滿足辯方總分和控方總分的差的絕對值最小。如果有多種選擇方案的辯方總分和控方總分的之差的絕對值相同,那么選辯控雙方總分之和最大的方案即可。最終選出的方案稱為陪審團方案。
                為敘述問題方便,現將任一選擇方案中,辯方總分和控方總分之差簡稱為“辯控差”,辯方總分和控方總分之和稱為“辯控和”。第i 個候選人的辯方總分和控方總分之差記為V(i),辯方總分和控方總分之和記為S(i)。現用f(j, k)表示,取j 個候選人,使其辯控差為k 的所有方案中,辯控和最大的那個方案(該方案稱為“方案f(j, k)”)的辯控和。并且,我們還規定,如果沒法選j 個人,使其辯控差為k,那么f(j, k)的值就為-1,也稱方案f(j, k)不可行。本題是要求選出m 個人,那么,如果對k 的所有可能的取值,求出了所有的f(m, k) (-20×m≤ k ≤ 20×m),那么陪審團方案自然就很容易找到了。
                問題的關鍵是建立遞推關系。需要從哪些已知條件出發,才能求出f(j, k)呢?顯然,方案f(j, k)是由某個可行的方案f(j-1, x)( -20×m ≤ x ≤ 20×m)演化而來的。可行方案f(j-1, x)能演化成方案f(j, k)的必要條件是:存在某個候選人i,i 在方案f(j-1, x)中沒有被選上,且x+V(i) = k。在所有滿足該必要條件的f(j-1, x)中,選出 f(j-1, x) + S(i) 的值最大的那個,那么方案f(j-1, x)再加上候選人i,就演變成了方案 f(j, k)。這中間需要將一個方案都選了哪些人都記錄下來。不妨將方案f(j, k)中最后選的那個候選人的編號,記在二維數組的元素path[j][k]中。那么方案f(j, k)的倒數第二個人選的編號,就是path[j-1][k-V[path[j][k]]。假定最后算出了解方案的辯控差是k,那么從path[m][k]出發,就能順藤摸瓜一步步求出所有被選中的候選人。初始條件,只能確定f(0, 0) = 0。由此出發,一步步自底向上遞推,就能求出所有的可行方案f(m, k)( -20×m ≤ k ≤ 20×m)。實際解題的時候,會用一個二維數組f 來存放f(j, k)的值。而且,由于題目中辯控差的值k 可以為負數,而程序中數租下標不能為負數,所以,在程序中不妨將辯控差的值都加上400,以免下標為負數導致出錯,即題目描述中,如果辯控差為0,則在程序中辯控差為400。

            #include <iostream>
            using namespace std;

            int p[201],d[201],result[21];
            int dp[21][801],path[21][801];

            int cmp(const void *a,const void *b){
                
            return *(int *)a-*(int *)b;
            }

            bool select(int a,int b,int i){
                
            while(a>0 && path[a][b]!=i){
                    b
            -=p[path[a][b]]-d[path[a][b]];
                    a
            --;
                }

                
            return (a!=0)?true:false;
            }

            int main(){
                
            int i,j,k,a,b,n,m,origin,ca=1;
                
            while(scanf("%d %d",&n,&m),n||m){
                    
            for(i=1;i<=n;i++)
                        scanf(
            "%d %d",p+i,d+i);
                    memset(dp,
            -1,sizeof(dp));
                    memset(path,
            0,sizeof(path));
                    origin
            =m*20;
                    
            for(dp[0][origin]=j=0;j<m;j++)
                        
            for(k=0;k<=origin*2;k++)
                            
            if(dp[j][k]>=0){
                                
            for(i=1;i<=n;i++)
                                    
            if(dp[j+1][k+p[i]-d[i]]<dp[j][k]+p[i]+d[i]){
                                        a
            =j,b=k;
                                        
            if(!select(a,b,i)){
                                            dp[j
            +1][k+p[i]-d[i]]=dp[j][k]+p[i]+d[i];
                                            path[j
            +1][k+p[i]-d[i]]=i;
                                        }

                                    }

                            }

                    
            for(i=origin,j=0;dp[m][i+j]<0 && dp[m][i-j]<0;j++);
                    k
            =dp[m][i+j]>dp[m][i-j]?i+j:i-j;
                    printf(
            "Jury #%d\n",ca++);
                    printf(
            "Best jury has value %d for prosecution and value %d for defence:\n",(dp[m][k]+k-origin)/2, (dp[m][k]-k+origin)/2);
                    
            for(i=1;i<=m;i++){
                        result[i]
            =path[m-i+1][k];
                        k
            -=p[result[i]]-d[result[i]];
                    }

                    qsort(result
            +1,m,sizeof(int),cmp);
                    
            for(i=1;i<=m;i++)
                        printf(
            " %d",result[i]);
                    printf(
            "\n");
                    printf(
            "\n");
                }

                
            return 0;
            }


             

            posted on 2009-06-23 17:08 極限定律 閱讀(4773) 評論(6)  編輯 收藏 引用 所屬分類: ACM/ICPC

            評論

            # re: POJ 1015 Jury Compromise 動態規劃 2009-09-09 14:03 boa

            不知道為什么這種方法uva和tju上是wa啊?難道是這兩個網站不判special judge?  回復  更多評論   

            # re: POJ 1015 Jury Compromise 動態規劃 2010-05-06 23:03 Cre_nws

            麻煩問一下" if(dp[j+1][k+p[i]-d[i]]<dp[j][k]+p[i]+d[i])"當k=0時,p[i]-d[i]如果為負值,那么會不會產生運行時錯誤啊?!謝啦!  回復  更多評論   

            # re: POJ 1015 Jury Compromise 動態規劃 2010-08-05 22:33 cxb

            @Cre_nws
            k應該不會取到0,因為取到0就意味著“辯控差”為負的最大,即已經到了j=m-1次循環,并且所有的陪審員都是p:0 s:20,此時k=0,并且整個循環已經結束了,這就是板主為何要將origin=m*20的原因之所在。有不對的地方,請指正~  回復  更多評論   

            # re: POJ 1015 Jury Compromise 動態規劃 2010-09-03 14:58 tel

            效率不是很高啊  回復  更多評論   

            # re: POJ 1015 Jury Compromise 動態規劃 2010-10-14 19:59 songtianyi

            效率已經不錯了  回復  更多評論   

            # re: POJ 1015 Jury Compromise 動態規劃 2011-08-05 20:33 asdf

            這個算法有后效性吧。就是在i的選取上。  回復  更多評論   

            <2025年7月>
            293012345
            6789101112
            13141516171819
            20212223242526
            272829303112
            3456789

            導航

            統計

            常用鏈接

            留言簿(10)

            隨筆分類

            隨筆檔案

            友情鏈接

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            日韩欧美亚洲综合久久影院Ds| 伊人久久大香线蕉综合Av| 欧美亚洲国产精品久久| 久久久免费精品re6| 97精品伊人久久大香线蕉app| 精品久久久久久| 久久婷婷色香五月综合激情 | 2021最新久久久视精品爱| 亚洲综合精品香蕉久久网| 91性高湖久久久久| 国内精品伊人久久久久AV影院| 亚洲欧美另类日本久久国产真实乱对白| 日韩av无码久久精品免费| 久久久久99精品成人片三人毛片 | 久久精品国产99国产精品| 中文字幕热久久久久久久| 国产一区二区三精品久久久无广告| 久久丫精品国产亚洲av| 日韩精品无码久久一区二区三| 97超级碰碰碰久久久久| 久久国产劲爆AV内射—百度| 欧美久久天天综合香蕉伊| 久久精品中文无码资源站| 亚洲国产成人久久一区久久| 国产精品久久亚洲不卡动漫| 一本色道久久HEZYO无码| 亚洲人成网站999久久久综合 | 一本一本久久a久久精品综合麻豆| 国产精品久久自在自线观看| 亚洲精品无码久久久久久| 亚洲国产精品18久久久久久| 久久伊人中文无码| 伊人久久大香线蕉综合5g| 青青国产成人久久91网| 国产综合免费精品久久久| 久久亚洲国产中v天仙www| 久久久久久久综合日本亚洲| 久久99精品综合国产首页| 久久精品成人国产午夜| 欧美久久综合性欧美| 94久久国产乱子伦精品免费|