Tug of War

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

3
100
90
200

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;
}