动态规划：正整数分组

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

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

动态规划解决：

递推公式：

  f(i,j)= {   f(i−1,j),                 如果 (j<ai)

    max(f(i−1,j),f(i,j−ai)+ai),          如果 (ai<=j<=[sum/2])  

#include<iostream> #include<cmath> using namespace std; int findMinDiff(int a[],int n){ int sum =0; for(int i=1;i<=n;i++){ sum+=a[i]; } int res[sum+1] = {0}; for(int i=1;i<=n;i++){ for(int j = sum/2;j>=a[i];j--) res[j] = max(res[j],res[j-a[i]]+a[i]); } return abs(sum-res[sum/2]-res[sum/2]); } int main() { int n; cin>>n; int a[n+1]; a[0]=0; for(int i=1;i<=n;i++) cin>>a[i]; cout<<findMinDiff(a,n); return 0; }