pku 2148 Cow Exhibition_综合

2184 Cow Exhibition 0－1背包问题变形，选定一个值作状态后，另一值可被标识。如果有更多信息需记录（信息量－1）的数组应该可以的。http://acm.pku.edu.cn/JudgeOnline/problem?id=1717 Dominos这道题也是一道类似的题目，
还可以用搜索来做。把有利的值统统加入，同时记下可能使不符合的元素，做一次排除，找到正确的最优值。

0－1背包有时（分堆）可以用随机贪心来做的，大致思路是从多的一堆中随机一个放入少的一堆中。

#include < iostream >
#define N 101
using namespace std;

int f[N],s[N];
int n,num;
int total;
int tF,tS;

int findProper( int a, int b, int idx)
{
     if (a >= 0 && b >= 0 )
    {
         if (a + b > total)
            total = a + b;
         return a + b;
    }
     if (idx >= num || a + b < total)
         return 0 ;
     int i = findProper(a,b,idx + 1 );
     int j = findProper(a + f[idx],b + s[idx],idx + 1 );
     return max(i,j);
}

int main()
{
     int i;
    scanf( " %d " , & n);
    total = tF = tS = num = 0 ;

     int a,b;
     for (i = 0 ; i < n; ++ i)
    {
        scanf( " %d%d " , & a, & b);

         if (a >= 0 && b >= 0 )
        {
            total += a + b;
            tF += a;
            tS += b;
        }
         else if (a * b <= 0 )
        {
             if (a + b > 0 )
            {
                tF += a;
                tS += b;
                a = - a;
                b = - b;
            }
            f[num] = a;
            s[num] = b;
             ++ num;
        }
    }
    printf( " %d " ,findProper(tF,tS, 0 ));
}