Rectangle(csu)

Description

Now ,there are some rectangles. The area of these rectangles is 1* x or 2 * x ,and now you need find a big enough rectangle( 2 * m) so that you can put all rectangles into it(these rectangles can't rotate). please calculate the minimum m satisfy the condition.

Input

There are some tests ,the first line give you the test number.
Each test will give you a number n (1<=n<=100)show the rectangles
number .The following n rows , each row will give you tow number a and
b. (a = 1 or 2 , 1<=b<=100).

Output

Each test you will output the minimum number m to fill all these rectangles.

Sample Input

2

3

1 2

2 2

2 3

3

1 2

1 2

1 3

Sample Output

7

4

Hint

只能说经验不足，不知道这道题是0 1背包，背包大小 sum/2

记忆化搜索

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <iostream>

#include <set>

using namespace std;

int num[120];

int n;

int maxhave[10000][120];

int getmax(int sum,int n)

{

    int res;

    if(maxhave[sum][n] != -1) res = maxhave[sum][n];

    else if(n == 1){

        if(sum >= num[n]) res = num[n];

        else res = 0;

    }

    else if(sum >= num[n]){

        res = max(getmax(sum - num[n],n - 1) + num[n],getmax(sum,n - 1));

    }

    else res = getmax(sum,n - 1);

    maxhave[sum][n] = res;

    return res;

}

int main()

{

    int t;

    cin>>t;

    while(t--){

        memset(maxhave,-1,sizeof maxhave );

        cin>>n;

        int ans,sum;

        int a,b,c=1;

        ans = sum = 0;

        for(int i = 1; i <= n; ++i)

        {

            cin>>a>>b;

            if(a == 2) ans += b;

            else { num[c++] = b;sum += b; }

        }

        --c;

        int tmp = getmax(sum/2,c);

        ans = ans + max(tmp,sum-tmp);

        cout<<ans<<endl;

    }

}