[51nod] 1007 正整数分组 dp

将一堆正整数分为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示例

1

此题可以转换为0-1背包问题，总和为sum, 选定一堆，求出不超过 j 的最大值，那么另一堆的和就可求出，找出其中的最小值即可
物品的重量和价格是一样的

#include <iostream>

#include <stdio.h>

#include <cstring>

#include <math.h>

#include <algorithm>

using namespace std;

#define INF 0x3f3f3f3f

int N;

int a[];

int dp[];

int sum;

int main()

{

    //freopen("1.txt", "r", stdin);

    cin >> N;

    for (int i = ; i <= N; i++) {

        cin >> a[i];

        sum += a[i];

    }

    memset(dp, , sizeof(dp));

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

        if (a[] <= i)

            dp[i] = a[];

        else

            dp[i] = ;

    for (int i = ; i <= N; i++) {

        for (int j = sum; j >= ; j--) {   //滚动数组，从右往左

            if (j >= a[i])

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

        }

    }

    int ret = INF;

    for (int i = ; i <= sum; i++) {

        ret = min(ret, abs(sum-*dp[i]));

    }

    cout << ret;

    return ;

}

其实最小值是两堆分别从左右逼近sum/2时取得，所以可以求不超过sum/2的最大值，这样就出来的差值就是最小值

#include <iostream>

#include <stdio.h>

#include <cstring>

#include <math.h>

#include <algorithm>

using namespace std;

int N;

int a[];

int dp[];

int sum;

int main()

{

    //freopen("1.txt", "r", stdin);

    cin >> N;

    for (int i = ; i <= N; i++) {

        cin >> a[i];

        sum += a[i];

    }

    int h = sum/;

    memset(dp, , sizeof(dp));

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

        if (a[] <= i)

            dp[i] = a[];

        else

            dp[i] = ;

    for (int i = ; i <= N; i++) {

        for (int j = h; j >= ; j--) {   //滚动数组，从右往左

            if (j >= a[i])

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

        }

    }

    int ret;

    ret = abs(sum - *dp[h]);

    cout << ret;

    return ;

}

巴特西

[51nod] 1007 正整数分组 dp

最新文章

热门文章