邮票分你一半

描写
     小珂最近搜集了些邮票,他想把其中的1些给他的好朋友小明。每张邮票上都有分值,他们想把这些邮票分成两份,并且使这两份邮票的分值和相差最小(就是小珂得到的邮票分值和与小明的差值最小),现在每张邮票的分值已知道了,他们已分好了,你知道最后他们得到的邮票分值和相差多少吗?

输入
第1行只有1个整数m(m<=1000),表示测试数据组数。
接下来有1个整数n(n<=1000),表示邮票的张数。
然后有n个整数Vi(Vi<=100),表示第i张邮票的分值。
输出
输出差值,每组输出占1行。
样例输入
2
5
2 6 5 8 9
3
2 1 5
样例输出
0
2
这题乍1看像是摹拟或搜索,但是由于数量级和时间的限制,感觉会超时,后来再仔细想一想,其实本质就是0⑴背包问题。
我们将分值总和的1半作为总的时间, 邮票的价值既是价值又是花费时间,所以这题就转化为在固定时间取得的最大值。
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define N 1005
int a[N];
int d[50005];
int n;
int main(){
	int t, i, j;
	scanf("%d", &t);
	while (t--){
		memset(d, 0, sizeof(d));
		scanf("%d", &n);
		int sum = 0;
		for (i = 0; i < n; i++){
			scanf("%d", &a[i]);
			sum += a[i];
		}
		for (i = 0; i < n; i++){
			for (j = sum / 2; j >= a[i]; j--){
				d[j] = max(d[j], d[j - a[i]] + a[i]);
			}
		}
		int res = (sum / 2 - d[sum / 2]) * 2;
		if (sum % 2 != 0)
			res++;
		printf("%d
", res);
	}
	return 0;
}


波比源码 – 精品源码模版分享 | www.bobi11.com
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 本站源码并不保证全部能正常使用,仅供有技术基础的人学习研究,请谨慎下载
8. 如遇到加密压缩包,请使用WINRAR解压,如遇到无法解压的请联系管理员!

波比源码 » 邮票分你一半

发表评论

Hi, 如果你对这款模板有疑问,可以跟我联系哦!

联系站长
赞助VIP 享更多特权,建议使用 QQ 登录
喜欢我嘛?喜欢就按“ctrl+D”收藏我吧!♡