HDU 1171Big Event in HDU（转01背包）

题意：

给你一组数，分成差距最小的两份A,B（A>=B）

分析：

转01背包

注意：

01背包用一维数组

不要用二维

　　二维数组若是开太大，内存超限，开太小，RE

#include "cstdio"

#include "cmath"

#include "cstring"

#include "iostream"

#include "algorithm"

using namespace std;

#define LL long long

#define N 250002

int dp[N];

int v[N];

int solve(int num,int W)

{

for(int i = 0;i < num;i++)

{

for(int j = W;j >= v[i];j--)

{

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

}

}

return dp[W];

}

int main()

{

int t;

while(scanf("%d",&t),(t>0))

{

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

memset(v,0,sizeof(v));

int num=0,sum=0;

int v1,n1;

while(t--)

{

scanf("%d%d",&v1,&n1);

for(int i=0;i

{

v[num++]=v1;

sum+=v1;

}

}

int W=sum/2;

int s=solve(num,W);

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

}

return 0;

}

推荐链接