题目 ：http://www.51nod.com/Challenge/Problem.html#!#problemId=1007
大意就是给一堆正整数，分成和最接近的两组。
最开始没什么想法，2^n尝试肯定TLE。查了查发现用的居然是dp.于是又回去看了一下dp算法，大概理解了。
先贴ac代码
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath> using namespace std; const int MAX = ; int source[];
int r[][MAX+]; int max(int a,int b)
{
return (a>b?a:b);
} int main()
{
int n=;
int i=;
int j=; int total=;
int half=; cin>>n; for(i=;i<n;i++)
{
scanf("%d",&source[i]);
total+=source[i]; //记得考虑最后total是奇数的情况。
} half=(total% == ?total/:total/+); for(i=;i<;i++)
{
r[i][]=;
} for(i=;i<n;i++)
{
for(j=;j<=half;j++)
{
if(source[i]>j) //r[i][j-1]=r[i-1][j]=r[i-1][j-1]
{
r[i][j]=r[i][j-];
}
else
{
if(i == )
{
r[i][j]=+source[i];
}
else
{
r[i][j]=max(r[i-][j],r[i-][j-source[i]]+source[i]);
}
}
} } cout<<abs(total-*r[n-][half]); return ;
}
之前在网上查，大部分人都说是01背包，但当时怎么都理解不了……于是换了一种思路：
dp方法最关键的步骤在于对于要求的问题 Q(n) ,它的答案一定是和之前求过的答案 Q(0) , Q(1) , Q(2) ... Q(n-1) 中的某个答案是有关系的。就这道题目来说，思考的方法是：记Q(n)为给定数中和不超过n的最大组合。就是给定数随便挑，只要和不大于n就行，我们要的是和最大的那组。
虽然是给定数随便挑，但我们也只能从第一个开始一个一个地看啊。于是，用记m为我们已经看了多少个数。
于是关键来了。假设我们从前m个数中，找到了一组小于n的最大值（仅仅在前m个数中是最大的，对于前m+1个数就不一定了），也就是说，我们暂时找到了Q(n)。但是因为所有的数还没看完，同时n还没达到目标（所有数的总和除以2）。那么，我们来考虑Q(n+1)，有如下几种情况：
1）Q(n)=Q(n-1),也就是说不需要m+1.那么有两种情况不需要：如果m+1>n,那么肯定Q(n)=Q(n-1)。因为m+1本来就不满足“小于n”。而如果m+1<n，那么也有可能不选，即没有合适的组合。那什么情况下没有合适的组合呢？就是从 1 到 m 随便怎么组合，只要加上m+1，要么大于n，要么小于Q(n-1)。
2）Q(n)>Q(n-1),根据上面的分析，这里就意味着有这么一个组合，能满足它加上m+1，正好介于Q(n-1)和n之间。那这个组合应该怎么找呢？换个思路，我们要找的Q(n)是小于n的最大和，我们知道这个数是k+(m-1)，而我们现在要找到 最大的k 。而恰好我们已经找到了从0到n-1的所有的最大值，因此那个k肯定在这之中，确切来说就是Q(n-(m+1)).
到此，思路就清晰了。