1007 正整数分组

1007 正整数分组

基准时间限制：1 秒 空间限制：131072 KB 分值: 10 难度：2级算法题

收藏

关注

将一堆正整数分为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
一开始看到题目,没怎么想就用了优先队列,结果有三组数据没过,就很纳闷,还以为是哪里错了呢,
然后仔细看了一下题,告诉了我们一个条件就是所有和,都不知道告诉我们是有什么意义,之后才发现
这是一道动归题.
化成01背包就解决了,弄得自己一头雾水.

#include <bits/stdc++.h>
using namespace std;
int k[105];
int dp[10005];
int main(){
  int n,sum=0;
  scanf("%d",&n);
  for(int i=0;i<n;i++){
    scanf("%d",&k[i]);
    sum+=k[i];
  }
  int N=sum/2;
  for(int i=0;i<n;i++){
    for(int j=N;j>=k[i];j--){
      dp[j]=max(dp[j],dp[j-k[i]]+k[i]);
    }
  }
  printf("%d
",abs(sum-dp[N]-dp[N]));
  return 0;
}