hdu 1171 Big Event in HDU

题目大意：hdu的计算机要分成两个学院，现在有n种物品，价值为ai的有bi个，要求把这些东西分成价值总和最为接近的两份，如果不能平分，大的在前面。

编程教训：
1、//(遍历每一括号时注意)循环的次数应该等于这一括号里表达式的最高指数

for(i=0;i<=v[1]*m[1];i+=v[1])
            c1[i]=1;

2、两个括号相乘之后（合并之后），这个括号的最高指数为len=v[1]*m[1]+v[i]*m[i]
  要注意保存中间结果，有点类似动态规划了

3、v[i]是作为增量的，括号里的项数由 增量与最高指数 表示

这样的话，看一下一半质量的组成方案是否可行（i=sum/2 c1[i]是否为1）：
行，直接输出；
不行，递增输出第一个不为0，另外一个sum-i(大的在前)

Input

Input contains multiple test cases. Each test case starts with a number N (0 < N <= 50 -- the total number of different facilities). The next N lines contain an integer V (0A test case starting with a negative integer terminates input and this test case is not to be processed

Sample Input

N是种类，价值为V的数量M，一共N种，以-1结尾

2
10 1
20 1
3
10 1
20 2
30 1
 -1

Sample Output

20 10
40 40

#include<stdio.h>
#include<string.h>

int c1[250010],c2[250010];//50 * 50 * 100;
int v[55],m[55];//M<=50个<V,M>,每一个最大值50*100

//(遍历每一括号时注意)循环的次数应该等于这一括号里表达式的最高指数
int main()
{
    int N;
    while(scanf("%d",&N)!=EOF && N>0)
    {
        int i,j,k,_sum=0;
        memset(c1,0,sizeof(c1));
        memset(c2,0,sizeof(c2));

        //记得初始化啊，否则会影响下一次结果
        memset(v,0,sizeof(v));
        memset(m,0,sizeof(m));
        //<v,m>初始化，从1开始
        for(i=1;i<=N;i++)
        {
            scanf("%d %d",&v[i],&m[i]);
            _sum+=v[i]*m[i];
        }
        //计算第一个括号,记得要相乘啊！！因为最高指数是v[]*m[]
        for(i=0;i<=v[1]*m[1];i+=v[1])
            c1[i]=1;

        int len=v[1]*m[1];//保存上一个结果的长度

        //计算剩下的N-1个括号
            for(i=2;i<=N;i++)
            {
                for(j=0;j<=len;j++)
                {
                    for(k=0;k<=v[i]*m[i];k+=v[i])
                        c2[k+j]+=c1[j];//将第二个括号有系数的都加进去
                }
                len=len+v[i]*m[i];
                for(j=0;j<=len;j++)
                {
                    c1[j]=c2[j];
                    c2[j]=0;
                }
            }


            for(i=_sum/2;i>=0;i--)
            {
                if(c1[i]!=0)//从一半的开始
                {
                    printf("%d %d\n",_sum-i,i);
                    break;
                }

            }


        }
    return 0;
}