【nyoj-456】 邮票分你一半 （dp，0-1背包的中点问题）
题干：
邮票分你一半
时间限制：1000 ms | 内存限制：65535 KB
难度：3
描述
小珂最近收集了些邮票，他想把其中的一些给他的好朋友小明。每张邮票上都有分值，他们想把这些邮票分成两份，并且使这两份邮票的分值和相差最小（就是小珂得到的邮票分值和与小明的差值最小），现在每张邮票的分值已经知道了，他们已经分好了，你知道最后他们得到的邮票分值和相差多少吗？
输入
第一行只有一个整数m（m<=1000),表示测试数据组数。
接下来有一个整数n(n<=1000)，表示邮票的张数。
然后有n个整数Vi(Vi<=100)，表示第i张邮票的分值。
输出
输出差值，每组输出占一行。
样例输入
2
5
2 6 5 8 9
3
2 1 5 样例输出
0
2
解题报告：
这题看起来很简单但是其实还是有坑的！下面提供n多中ac的代码。坑就在于 ，sum有可能是奇数！！
AC代码：（网络版，至今不知为什么这么做可以，普通0-1背包）
#include<bits/stdc++.h>
using namespace std;
int n;
int v[1000 + 5];
int dp[100000 + 5];
int main()
{
int t;
int sum = 0;
cin>>t;
while(t--) {
sum = 0;
cin>>n;
for(int i = 1; i<= n; i++) {
scanf("%d",&v[i]);sum += v[i];
}
int yuan=sum;
sum=(sum+1)/2;//这里直接sum=sum/2 也可以ac！！！即 +1与否不影响
if(n == 1) {
cout << v[1] << endl; continue;
}
memset(dp,0,sizeof(dp));
for(int i = 1; i<=n; i++)
for(int j = sum; j>=v[i]; j--) {
if(abs(j-dp[j]) < abs(dp[j-v[i]]+v[i]-j)) dp[j]=dp[j];
else dp[j]=dp[j-v[i]]+v[i];
}
cout << abs(yuan-dp[sum]-dp[sum]) << endl;
}
return 0 ;
}
对于上面这种方法，我只理解到了下面的内容：
因为背包是一类问题，比如一般的0-1背包，你取dp[j] = max()，是因为你想得到价值最大的，所以你这个状态代表的是，前i个物品在j容量下的最大价值是dp[j]这么大。
所以对于这个题来说你想得到的是最接近一半的分值，所以你dp[j]中存的应该是最接近当前价值的， 即： 如果更接近当前价值，那我就更新他。
AC代码2：（也是普通0-1背包）
#include<bits/stdc++.h>
using namespace std;
int n;
int v[1000 + 5];
int dp[100000 + 5];
int main()
{
int t;
int sum = 0;
cin>>t;
while(t--) {
sum = 0;
cin>>n;
for(int i = 1; i<=n; i++) {
scanf("%d",&v[i]);sum += v[i];
}
int half = sum>>1 ;//这里用half = sum>>1 + 1就错了！！但是half = (sum+1)>>1是对的。。。当然你最后输出的时候需要加个abs()才能ac！！！
memset(dp,0,sizeof(dp));
for(int i = 1; i<=n; i++) {
for(int j = half; j>=v[i]; j--) {
dp[j] = max(dp[j],dp[j-v[i]] + v[i]);
}
}
cout << sum-2*dp[half]<<endl;
}
return 0 ;
} 最开始就是这么写的但是我的输出相当于是cout << 2*(half - dp[half] )<<endl;样例也过了，我也觉着我这样理解是没有问题的，举个例子：总分值为10，我3他7，那我俩的差值不就是 2*((10/2)-3)这么大吗？如果 我4他6，，也可以成立，然后就这么交上去了，然后wa。看了别人的代码才发现，原来是奇偶数出现了问题，因为我试的样例是偶数（10嘛），所以肯定看样例肯定看不出来问题，于是我就改成了保留原sum，新开一个half，然后最后输出的时候用sum去减，而不是2*half去减。也就是把最后的输出改成了AC代码中那样的形式。
AC代码3：（装满型0-1背包）
#include<bits/stdc++.h>
using namespace std;
int n;
int v[1000 + 5];
int dp[100000 + 5];
int main()
{
int t;
int sum = 0;
cin>>t;
while(t--) {
sum = 0;
cin>>n;
for(int i = 1; i<=n; i++) {
scanf("%d",&v[i]);sum += v[i];
}
// sum=(sum+1)/2;
if(n == 1) {
cout << v[1] << endl; continue;
}
memset(dp,-0x3f3f3f3f,sizeof(dp));dp[0] = 0;
for(int i = 1; i<=n; i++) {
for(int j = sum; j>=v[i]; j--) {
dp[j] = max(dp[j],dp[j-v[i]] + v[i]);
}
}
int minn = 0x3f3f3f3f;
for(int i = sum; i>=0; i--) {
if(dp[i] >=0) {
//cout << 2*(sum-dp[i])<<endl;break;
minn = min( abs(sum-dp[i]-dp[i]),minn);
}
}
cout << minn<<endl;
}
return 0 ;
} 这段代码，是我在写完AC代码2，然后WA了之后，重新改了一下，不再有sum/=2这样的操作，而是直接扫到sum，然后从后往前一个个的扫，维护一个minn，最后输出minn，这样也AC了但是时间是500ms左右，是AC代码1，AC代码2 的两倍左右
