Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <string.h>
- #include <stdlib.h>
- int ind[22501],dp[22501][2],dp2[22501][2],people,total,weight[100],top,top2,tmp,x=0;
- double a,b;
- int cmp(const void *a , const void *b ) {
- return *(int *)a - *(int *)b;
- }
- int main() {
- int i,j,k,n,tmp,answer;
- scanf("%d",&n);
- while(n-- > 0) {
- memset(dp2,0,sizeof(dp2));
- x++;
- total = 0;
- scanf("%d",&people);
- for(i=0; i<people; i++) {
- scanf("%d",&weight[i]);
- total += weight[i];
- }
- qsort(weight,people,sizeof(weight[0]),cmp);
- dp2[0][0] = 0;
- dp2[0][1] = -1;
- top2 = 1;
- for(i=0; i<(people+1)/2; i++) {
- memcpy(dp,dp2,sizeof(dp));
- memset(ind,0,sizeof(ind));
- top = top2;
- top2 = 0;
- for(j=i; j<people; j++) {
- for(k=0; k<top; k++) {
- tmp = dp[k][0] + weight[j];
- if(j <= dp[k][1])
- break;
- if(tmp <= total/2) {
- if(ind[tmp] == 0) {
- dp2[top2][0] = tmp;
- dp2[top2++][1] = j;
- ind[tmp] = 1;
- }
- }
- else
- break;
- }
- }
- }
- answer = dp2[top2-1][0];
- if(people%2 != 0 && dp[top-1][0] > answer)
- answer = dp[top-1][0];
- printf("%d %d\n",answer,total-answer);
- if(n != 0)
- printf("\n");
- }
- }
Add Comment
Please, Sign In to add comment