传送门：http://poj.org/problem?id=1015

大概就是有m个人，每个人有一个d值一个p值，从m个人中选出n个人，使得他们的d值和与p值和之差的绝对值最小，若有多个答案两数之差相同选其中d值和与p值和最大的。

也是背包问题。二维数组，dp[i][j]，取i个人，差值为j，和放在dp[i][j]中，path[i][j]记录路径。

由于下标没有负数，将整个数组向右移动400（20*20）个单位。400为差值为0的地方。

//整理好思路再进行编程真的会更高效——来自一个没有事先思考好就敲键盘结果最后改了老半天程序的渣渣

1 #include
     
       2 #include
      
        3 #include
       
         4 using namespace std;  5 int main(){ 6     int n,m; 7     int dp[21][801]; 8     int d[200]; 9     int p[200];10     int path[21][801];11     int Jury[20];12     int k=1;13     while(cin>>n>>m){14         if(n==0&&m==0){15             break;16         }17         for(int i=0;i
        
         >d[i]>>p[i];19         }20         int SD=20;21         memset(dp,-1,sizeof(dp));22         dp[0][400]=0;23         memset(path,-1,sizeof(path));24         for(int i=1;i<=m;i++){25             for(int j=400-SD*(i-1);j<=400+SD*(i-1);j++){26                 if(dp[i-1][j]>=0){27                     for(int t=0;t
         
          0;T1--){32                             T2=path[T1][T3];33                             if(T2==t){34                                 flag=false;35                                 break;    36                             }37                             T3=T3-(d[T2]-p[T2]);38                         }39                         if(flag&&((dp[i-1][j]+d[t]+p[t])>dp[i][j+d[t]-p[t]])){40                             dp[i][j+d[t]-p[t]]=dp[i-1][j]+d[t]+p[t];41                             path[i][j+d[t]-p[t]]=t;42                         }43                     }44                 }45             }46         }47         int biaozhi;48         for(int cha=0;cha<=SD*m;cha++){49             if(dp[m][400+cha]>=0||dp[m][400-cha]>=0){50                 biaozhi=dp[m][400+cha]>dp[m][400-cha]?400+cha:400-cha;51                 break;52             }53         }54         int T2;55         for(int T1=m;T1>0;T1--){56             T2=path[T1][biaozhi];57             Jury[T1-1]=T2;58             biaozhi=biaozhi-(d[T2]-p[T2]);59         }60         sort(Jury,Jury+m);61         int sumD=0;62         int sumP=0;63         for(int i=0;i