[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示例

5
1
2
3
4
5

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[110];
int dp[10010];
int sum;


int main()
{
    //freopen("1.txt", "r", stdin);
    cin >> N;
    for (int i = 1; i <= N; i++) {
        cin >> a[i];
        sum += a[i];
    }
    
    memset(dp, 0, sizeof(dp));
    for (int i = 0; i <= sum; i++)
        if (a[1] <= i)
            dp[i] = a[1];
        else
            dp[i] = 0;

    for (int i = 2; i <= N; i++) {
        for (int j = sum; j >= 0; j--) {   //滚动数组，从右往左
            if (j >= a[i])
                dp[j] = max(dp[j], dp[j-a[i]]+a[i]);
        }
    }

    int ret = INF;
    for (int i = 0; i <= sum; i++) {
        ret = min(ret, abs(sum-2*dp[i]));
    }
    cout << ret;


    return 0;
}

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

#include <iostream>
#include <stdio.h>
#include <cstring>
#include <math.h>
#include <algorithm>
using namespace std;

int N;
int a[110];
int dp[10010];
int sum;


int main()
{
    //freopen("1.txt", "r", stdin);
    cin >> N;
    for (int i = 1; i <= N; i++) {
        cin >> a[i];
        sum += a[i];
    }

    int h = sum/2;
    memset(dp, 0, sizeof(dp));
    for (int i = 0; i <= h; i++)
        if (a[1] <= i)
            dp[i] = a[1];
        else
            dp[i] = 0;

    for (int i = 2; i <= N; i++) {
        for (int j = h; j >= 0; j--) {   //滚动数组，从右往左
            if (j >= a[i])
                dp[j] = max(dp[j], dp[j-a[i]]+a[i]);
        }
    }

    int ret;
    ret = abs(sum - 2*dp[h]);
    cout << ret;


    return 0;
}