51Nod 1007 正整数分组（01背包）

将一堆正整数分为2组，要求2组的和相差最小。

例如：1 2 3 4 5，将1 2 4分为1组，3 5分为1组，两组和相差1，是所有方案中相差最少的。

Input

第1行：一个数N，N为正整数的数量。

第2 - N+1行，N个正整数。

(N <= 100, 所有正整数的和 <= 10000)

Output

输出这个最小差

Input示例

Output示例

#include <iostream>

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <vector>

#include <queue>

#include <stack>

#include <cstdlib>

#include <iomanip>

#include <cmath>

#include <cassert>

#include <ctime>

#include <map>

#include <set>

using namespace std;

#pragma comment(linker, "/stck:1024000000,1024000000")

#define lowbit(x) (x&(-x))

#define max(x,y) (x>=y?x:y)

#define min(x,y) (x<=y?x:y)

#define MAX 100000000000000000

#define MOD 1000000007

#define pi acos(-1.0)

#define ei exp(1)

#define PI 3.1415926535897932384626433832

#define ios() ios::sync_with_stdio(true)

#define INF 0x3f3f3f3f

#define mem(a) ((a,0,sizeof(a)))

typedef long long ll;

int dp[],a[],n;

int ans=,pos;

int main()

{

    scanf("%d",&n);

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

    {

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

        ans+=a[i];

    }

    memset(dp,,sizeof(dp));

    pos=ans/;

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

    {

        for(int j=pos;j>=a[i];j--)

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

    }

    int cnt=;

    for(int i=;i<=pos;i++)

        cnt=max(cnt,dp[i]);

    //printf("%d\n",cnt);

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

    return ;

}

秒客网

51Nod 1007 正整数分组（01背包）

相关文章