【0-1背包】正整数分组

51nod p1007

将一堆正整数分为2组,要求2组的和相差最小。
例如:1 2 3 4 5,将1 2 4分为1组,3 5分为1组,两组和相差1,是所有方案中相差最少的。

输入

第1行:一个数N,N为正整数的数量。
第2 - N+1行,N个正整数。
(N <= 100, 所有正整数的和 <= 10000)

输出

输出这个最小差

输入样例

5
1
2
3
4
5

输出样例

1

分析:

把所有的数加在一起,那么最小的一组必定值不会超过sum/2.问题转化成如何在容量为sum/2的背包中选择合适的数然后使之sum最大,每个数的价值与成本相同。

AC代码:

#include <iostream>
#include <algorithm>
#include <cmath>
using  namespace std;
typedef long long LL;
int arr[10005];
int dp[10005];
int main()
{
  int n = 0;
  cin >> n;
  int sum = 0;
  for (int i = 1; i <= n; i++)
  {
    cin >> arr[i];
    sum += arr[i];
  }
  for (int i = 1; i <= n; i++)
  {
    for (int j = sum / 2; j >= arr[i]; j--)//背包容量为sum/2,设dp[sum/2]为较小的那一组的和
      dp[j] = max(dp[j], dp[j - arr[i]] + arr[i]);
  }
  cout << (sum - dp[sum / 2]) - dp[sum / 2] << endl;
}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注

5 × 1 =