HDU 1171 Big Event in HDU(01背包）

题目地址：HDU 1171

还是水题。

。

普通的01背包。注意数组要开大点啊。

。。。

代码例如以下：

#include <iostream>

#include <cstdio>

#include <string>

#include <cstring>

#include <stdlib.h>

#include <math.h>

#include <ctype.h>

#include <queue>

#include <map>

#include <set>

#include <algorithm>

using namespace std;

int dp[260000], v[600], k[600], c[260000];

int main()

{

    int n, i, j, y, z, sum, s, cnt, x;

    while(scanf("%d",&n)!=EOF)

    {

        if(n<0) break;

        sum=0;

        for(i=0;i<n;i++)

        {

            scanf("%d%d",&v[i],&k[i]);

            sum+=v[i]*k[i];

        }

        memset(dp,0,sizeof(dp));

        cnt=0;

        for(i=0;i<n;i++)

        {

            x=k[i];

            y=1;

            while(x-y>=0)

            {

                c[cnt++]=y*v[i];

                x-=y;

                y*=2;

            }

            if(x)

                c[cnt++]=x*v[i];

        }

        s=sum;

        sum/=2;

        dp[0]=1;

        for(i=0;i<cnt;i++)

        {

            for(j=sum;j>=c[i];j--)

            {

                if(dp[j-c[i]])

                    dp[j]=1;

            }

        }

        int ans;

        for(i=sum;i>=0;i--)

        {

            if(dp[i])

            {

                ans=i;

                break;

            }

        }

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

    }

    return 0;

}