题目链接：http://acm.csu.edu.cn/csuoj/problemset/problem?pid=1547

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

Sample Output

7

4

Hint

Source

题意：

　　给你n个长方形（其中有宽为1的，也有宽为2的长方形），问你需要一个多大的宽为2的长方形才能将这些小长方形全部圈住（不能旋转长方形，即全部长方形为一个方向）。求最小m。

题解：

　　小长方形宽为2的时候 ans+= b，直接加。所以我们只要讨论宽为1的小长方形。

　　全部的宽为1的长方形我们所要做的就是将它们分成长度尽可能接近的2堆，我们就需要用01背包来解决。

　　背包的容量为sum/2（sum为全部宽为1长方形的b的和），每一个长方形的价值为b，当然重量也为b

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <cstdlib>

 #include <string>

 #include <vector>

 #include <map>

 #include <set>

 #include <queue>

 #include <sstream>

 #include <algorithm>

 using namespace std;

 #define pb push_back

 #define mp make_pair

 #define ms(a, b)  memset((a), (b), sizeof(a))

 //#define LOCAL

 #define eps 0.0000001

 typedef long long LL;

 const int inf = 0x3f3f3f3f;

 const int maxn = +;

 const int mod = ;

 int w[maxn];

 int dp[maxn*maxn];

 void solve()

 {

     ms(w, );

     ms(dp, );

     int n, a, b, ans=, sum = , cnt = ;

     scanf("%d", &n);

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

         scanf("%d%d", &a, &b);

         if(a==)    ans += b;

         else w[++cnt] = b, sum+=b;

     }

     for(int i=;i<=cnt;i++){

         for(int v = sum/; v>=w[i]; v--){

                 dp[v] = max(dp[v], dp[v-w[i]]+w[i]);

         }

     }

     ans += max(dp[sum/], sum-dp[sum/]);

     printf("%d\n", ans);

 }

 int main()

 {

     #ifdef LOCAL

         freopen("jumping.in", "r", stdin);

 //      freopen("output.txt", "w", stdout);

     #endif // LOCAL

     int T;

     scanf("%d", &T);

     while(T--){

         solve();

     }

     return ;

 }

总结：

1）了解到了如果将一个数堆分成最接近的2堆，可以转变成01背包。

比赛时还是靠队友过了XD。

巴特西

CSU 1547 Rectangle（dp、01背包）