CSU 1547: Rectangle （思维题加一点01背包）

1547: Rectangle

Time Limit: 1 Sec Memory Limit: 256 Mb Submitted: 1198 Solved: 347

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

题目意思：
现在有这样一些方块，1 x n和2 x n的方块
要你放进2 x m的大方块内（方块不重叠）
问你最小的m的值是多少

ans代表最小的m

分析：
在给出的方块中，宽为2的方块肯定是直接放进2 x m的大方块中的
所以ans直接加上这些宽为2的方块的长

现在没有放进去的方块中，只有宽度为1的了
所以我们应该尽可能的把这些方块分成尽可能相等的两部分
这样m才会最小
所以我们现在是把这些宽度为1，长度已知的方块采取尽可能好的策略放置

其实这就是一个01背包问题
背包容量就是所有宽度为1的方块的长
物品价值和重量都是这些宽度为1的方块的长

然后就是需要加上这些宽1的方块叠成的长的最大值

code：

#include<stdio.h>
#include<iostream>
#include<vector>
#include <cstring>
#include <stack>
#include <cstdio>
#include <cmath>
#include <queue>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include<string>
#include<string.h>
#include<math.h>
typedef long long LL;
using namespace std;
#define max_v 105
int b[max_v];//宽1的方块长
//01背包
int ZeroOnePack_improve(int v[],int w[],int n,int c)
{
    int dp[c+1];
    memset(dp,0,sizeof(dp));
    for(int i=1; i<=n; i++)
    {
        for(int j=c; j>=0; j--)
        {
            if(j>=w[i])
                dp[j]=max(dp[j],dp[j-w[i]]+v[i]);

        }
    }
    return dp[c];
}
void init()
{
    memset(b,0,sizeof(b));
}
int main()
{
    int t;
    scanf("%d",&t);
    int n;
    int x,y;
    while(t--)
    {
        init();
        scanf("%d",&n);
        //结果
        int ans=0;
        //宽为1的方块的总长
        int c=0;
        
        int m=0;
        for(int i=0; i<n; i++)
        {
            scanf("%d %d",&x,&y);
            if(x==2)
                ans+=y;
            else if(x==1)
                c+=y,b[++m]=y;
        }
        int w=ZeroOnePack_improve(b,b,m,c/2);
        ans+=max(c-w,w);//加上大的那个！！！ wa了几次....
        printf("%d
",ans);
    }
}
/*
题目意思：
现在有这样一些方块，1 x n和2 x n的方块
要你放进2 x m的大方块内（方块不重叠）
问你最小的m的值是多少

ans代表最小的m

分析：
在给出的方块中，宽为2的方块肯定是直接放进2 x m的大方块中的
所以ans直接加上这些宽为2的方块的长

现在没有放进去的方块中，只有宽度为1的了
所以我们应该尽可能的把这些方块分成尽可能相等的两部分
这样m才会最小
所以我们现在是把这些宽度为1，长度已知的方块采取尽可能好的策略放置

其实这就是一个01背包问题
背包容量就是所有宽度为1的方块的长
物品价值和重量都是这些宽度为1的方块的长

然后就是需要加上这些宽1的方块叠成的长的最大值

*/